C++ प्रोग्राम: BFS का उपयोग करके डायरेक्टेड ग्राफ की कनेक्टिविटी जांचना

ग्राफ की कनेक्टिविटी जांचने के लिए, हम किसी भी ट्रैवर्सल एल्गोरिदम का उपयोग करके सभी नोड्स को ट्रैवर्स करने का प्रयास करेंगे। ट्रैवर्सल पूरा होने के बाद, यदि कोई नोड है, जो विजिट नहीं हुआ है, तो ग्राफ कनेक्टेड नहीं है।

डायरेक्टेड ग्राफ के लिए, हम कनेक्टिविटी जांचने के लिए सभी नोड्स से ट्रैवर्स करना शुरू करेंगे। कभी-कभी एक एज का केवल आउटवर्ड एज हो सकता है लेकिन कोई इनवर्ड एज नहीं, इसलिए वह नोड किसी अन्य स्टार्टिंग नोड से अनविजिटेड रहेगा।

इस मामले में ट्रैवर्सल एल्गोरिदम रिकर्सिव BFS ट्रैवर्सल है।

इनपुट - ग्राफ का एडजेसेंसी मैट्रिक्स

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

आउटपुट - ग्राफ कनेक्टेड है।

एल्गोरिदम

traverse(s, visited)

इनपुट: स्टार्ट नोड s और विजिटेड नोड यह मार्क करने के लिए कि कौन सा नोड विजिट हुआ है।

आउटपुट: सभी कनेक्टेड वर्टेक्स को ट्रैवर्स करें।

Begin
    s को विजिटेड मार्क करें
    s को क्यू Q में डालें
    जब तक Q खाली न हो, करें
        u = क्यू से निकाला गया नोड
        ग्राफ के प्रत्येक नोड v के लिए, करें
            यदि u और v कनेक्टेड हैं, तो
                यदि u विजिट नहीं हुआ है, तो
                    u को विजिटेड मार्क करें
                    u को क्यू Q में डालें।
            किया
        किया
    किया
End

isConnected(graph)

इनपुट - ग्राफ।

आउटपुट - यदि ग्राफ कनेक्टेड है तो True।

Begin
    विजिटेड ऐरे परिभाषित करें
    ग्राफ में सभी वर्टेक्स u के लिए, करें
        सभी नोड्स को अनविजिटेड बनाएं
        traverse(u, visited)
        यदि कोई अनविजिटेड नोड अभी भी शेष है, तो
            false लौटाएं
    किया
    true लौटाएं
End

उदाहरण कोड

#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 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];
    // सभी वर्टेक्स u को स्टार्ट पॉइंट के रूप में, जांचें कि क्या सभी नोड्स विजिबल हैं या नहीं
    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.