মডিউল ৫_২ঃ Cycle Detection Undirected গ্রাফ BFS ইমপ্লিমেন্টশন

Cycle Detection Undirected গ্রাফ BFS ইমপ্লিমেন্টশন

আমরা এখন BFS দিয়ে cycle detection স্টেপ বাই স্টেপ কোড এ দেখার চেষ্টা করব।

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

int n, e;
cin >> n >> e;
while (e--)
{
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
}

এবার ভিজিটেড এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি false হিসেবে। parentArray এ্যারেটি ইনিশিয়ালাইজ করে নিচ্ছি -1 হিসেবে এবং ans কে false করে নিচ্ছি।

memset(vis, false, sizeof(vis));
memset(parentArray, -1, sizeof(parentArray));
ans = false;

এরপর number of nodes বার লুপ চালাচ্ছি এবং কোন নোড আনভিজিটেড হলে সেই নোডটি দিয়ে bfs function কে কল করতেছি।

for (int i = 0; i < n; i++)
{
    if (!vis[i])
    {
        bfs(i);
    }
}

প্রথমে source কে queue তে পুশ করবো, এরপর queue যতক্ষণ না empty হচ্ছে ততক্ষন লুপ চালাবো । লুপের মধ্যে queue থেকে front বের করে নিব এবং queue তে pop করে দিব। queue থেকে যে নোডটি front করে বের করা হয়েছে , সেইটির child বের করবো লুপ আরেকটি লুপ চালিয়ে, সেইখানে যদি child আনভিজিটেড এবং parent এর parrenyArray যদি child না হয় তাহলে গ্রাফটিতে cycle আছে, তখন ans = true করে মনে রাখবো। এরপর আনভিজিটেড child কে ভিজিটেড করবো এবং child টি parent সেট করে দিব parrentArray তে। এরপর child টিকে queue তে পুশ করে দিব।

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty())
    {
        int parent = q.front();
        // cout << parent << endl;
        q.pop();
        for (int child : adj[parent])
        {
            if (vis[child] == true && parentArray[parent] != child)
            {
                ans = true;
            }
            if (vis[child] == false)
            {
                vis[child] = true;
                parentArray[child] = parent;
                q.push(child);
            }
        }
    }
}

এইভাবে আমরা BFS দিয়ে undirected গ্রাফে cycle detect করতে পারি।

সম্পূর্ণ কোড Cycle Detection Undirected গ্রাফ BFS ইমপ্লিমেন্টশন

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool vis[N];
vector<int> adj[N];
int parentArray[N];
bool ans;
void bfs(int s)
{
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty())
    {
        int parent = q.front();
        // cout << parent << endl;
        q.pop();
        for (int child : adj[parent])
        {
            if (vis[child] == true && parentArray[parent] != child)
            {
                ans = true;
            }
            if (vis[child] == false)
            {
                vis[child] = true;
                parentArray[child] = parent;
                q.push(child);
            }
        }
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    memset(vis, false, sizeof(vis));
    memset(parentArray, -1, sizeof(parentArray));
    ans = false;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            bfs(i);
        }
    }
    if (ans)
    {
        cout << "Cycle found";
    }
    else
    {
        cout << "Cycle not found";
    }
    return 0;
}