C++ প্রোগ্রাম: BFS ব্যবহার করে ডিরেক্টেড গ্রাফের কানেক্টিভিটি চেক করা

একটি গ্রাফের কানেক্টিভিটি চেক করতে, আমরা যেকোনো ট্রাভার্সাল অ্যালগরিদম ব্যবহার করে সব নোড ট্রাভার্স করার চেষ্টা করব। ট্রাভার্সাল শেষে, যদি কোনো নোড থাকে যা ভিজিটেড নয়, তবে গ্রাফটি কানেক্টেড নয়।

ডিরেক্টেড গ্রাফের জন্য, আমরা সব নোড থেকে ট্রাভার্স শুরু করব কানেক্টিভিটি চেক করতে। কখনো কখনো একটি এজ শুধু আউটওয়ার্ড এজ থাকতে পারে কিন্তু ইনওয়ার্ড এজ নেই, তাই সেই নোড অন্য যেকোনো স্টার্টিং নোড থেকে আনভিজিটেড থাকবে।

এই কেসে ট্রাভার্সাল অ্যালগরিদম হলো রিকারসিভ BFS ট্রাভার্সাল।

ইনপুট - একটি গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স

আউটপুট - The Graph is connected.

অ্যালগরিদম

traverse(s, visited)

ইনপুট: স্টার্ট নোড s এবং ভিজিটেড নোড যাতে কোন নোড ভিজিটেড সেটি মার্ক করা যায়।

আউটপুট: সব কানেক্টেড ভার্টেক্স ট্রাভার্স।

শুরু
  s কে ভিজিটেড মার্ক করুন
  s কে একটি কিউ Q-তে ইনসার্ট করুন
  যতক্ষণ Q খালি নয়, করুন
    u = কিউ থেকে বের করা নোড
    গ্রাফের প্রতিটি নোড v এর জন্য, করুন
      if u এবং v কানেক্টেড, তবে
        if u ভিজিটেড নয়, তবে
          u কে ভিজিটেড মার্ক করুন
          u কে কিউ Q-তে ইনসার্ট করুন।
    লুপ শেষ
  লুপ শেষ
শেষ

isConnected(graph)

ইনপুট - গ্রাফ।

আউটপুট - True যদি গ্রাফ কানেক্টেড হয়।

শুরু
visited অ্যারে ডিফাইন করুন
গ্রাফের সব ভার্টেক্স u এর জন্য, করুন
  সব নোড আনভিজিটেড করুন
  traverse(u, visited)
  যদি কোনো আনভিজিটেড নোড থাকে, তবে
    return false
লুপ শেষ
return true
শেষ

উদাহরণ কোড

#include<iostream>
#include<queue>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 1, 1},
    {1, 0, 0, 0, 0},
    {0, 1, 0, 0, 0}
};

void traverse(int s, bool visited[]) {
    visited[s] = true; // v কে ভিজিটেড মার্ক
    queue<int> que;
    que.push(s); // s কে কিউতে ইনসার্ট
    while(!que.empty()) {
        int u = que.front(); // কিউ থেকে ডিলিট করুন
        que.pop();
        for(int i = 0; i < NODE; i++) {
            if(graph[i][u]) {
                // যখন নোড আনভিজিটেড
                if(!visited[i]) {
                    visited[i] = true;
                    que.push(i);
                }
            }
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false; // ইনিশিয়ালাইজ: কোনো নোড ভিজিটেড নয়
        traverse(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i]) // যদি কোনো নোড ট্রাভার্সালে ভিজিটেড নয়, গ্রাফ কানেক্টেড নয়
                return false;
        }
    }
    return true;
}

int main() {
    if(isConnected()) cout << "The Graph is connected.";
    else cout << "The Graph is not connected.";
}

আউটপুট

The Graph is connected.