মডিউল ২_২ঃ বিএফএস কোড ইমপ্লিমেন্টেশন

আমরা এখন বিএফএস ট্রাভারসাল এলগোরিদমটি স্টেপ বাই স্টেপ কোড এ দেখার চেষ্টা করব।

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> v[1005];
bool vis[1005];
void bfs(int src)
{
    queue<int> q;
    q.push(src);
    vis[src] = true;
    while (!q.empty())
    {
        int par = q.front();
        q.pop();
        cout << par << endl;
        for (int child : v[par])
        {
            if (vis[child] == false)
            {
                q.push(child);
                vis[child] = true;
            }
        }
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int src;
    cin >> src;
    memset(vis, false, sizeof(vis));
    bfs(src);
    return 0;
}
```

এখানে প্রথমে আমরা মেইন ফাংশনটি বোঝার চেষ্টা করব। প্রথমে আমরা নোড সংখ্যা ও এডজ সংখ্যা ইনপুট নিয়েছি। এরপর একটি লুপের মাধ্যমে কোন নোড দুইটির মধ্যে এডজ থাকবে সেটা অ্যাডজেসেন্সি লিস্ট এর মধ্যে নিয়ে নিচ্ছি।

// Some code
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

এবার সোর্স নোড ইনপুট নিয়ে ভিজিটেড এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি false হিসেবে। সবশেষে bfs ফাংশনকে কল করছি।

// Some code
    int src;
    cin >> src;
    memset(vis, false, sizeof(vis));
    bfs(src);

এবার আমরা চলে আসি আমাদের আসল কাজে বিএফএস ফাংশনে। এখানে একটি কিউ নিয়েছি। আর ইনিশিয়ালি সোর্স ভ্যালুকে কিউতে পুশ করে দিয়েছি। আর সোর্স নোডকে ভিজিটেড করে দিলাম।

// Some code
    queue<int> q;
    q.push(src);
    vis[src] = true;

এবার কিউ এম্পটি না হওয়া অব্দি একটি লুপ চালাবো ও প্রতিবার কিউ এর ফ্রন্ট ভ্যালুকে নিব। তাকে প্রিন্ট করে কিউ থেকে পপ করে দিব। ওই এলিমেন্ট এর অ্যাডজেসেন্সি লিস্টে যাব ও সেই লিস্ট এর মধ্যে যেসকল নোড আনভিজিটেড আছে সেইসকল নোডকে কিউতে পুশ করব ও তাদেরকে ভিজিটেড এ্যারেতে true করে দেব।

// Some code
   while (!q.empty())
    {
        int par = q.front();
        q.pop();
        cout << par << endl;
        for (int child : v[par])
        {
            if (vis[child] == false)
            {
                q.push(child);
                vis[child] = true;
            }
        }
    }

এই হয়ে গেল আমাদের বিএফএস ট্রাভারসাল।