अनडायरेक्टेड ग्राफ के कनेक्टेड कॉम्पोनेंट्स खोजने के लिए C++ प्रोग्राम

दिए गए अनडायरेक्टेड ग्राफ के लिए वीकली (Weakly) या स्ट्रॉन्गली (Strongly) कनेक्टेड होने का पता DFS का उपयोग करके लगाया जा सकता है। यह इस समस्या का C++ प्रोग्राम है।

उपयोग किए गए फंक्शन

Begin Function fillorder() = सभी वर्टेक्स को स्टैक में भरें।
    a) वर्तमान नोड को विज़िटेड मार्क करें और प्रिंट करें
    b) इस वर्टेक्स से आसन्न सभी वर्टेक्स के लिए रिकर्सन करें
    c) v से पहुंचने योग्य सभी वर्टेक्स अब प्रोसेस हो चुके हैं, v को स्टैक में पुश करें
End
Begin Function DFS() :
    a) वर्तमान नोड को विज़िटेड मार्क करें और प्रिंट करें
    b) इस वर्टेक्स से आसन्न सभी वर्टेक्स के लिए रिकर्सन करें
End

उदाहरण

#include <iostream> #include <list> #include <stack> using namespace std; class G {    int m;    list<int> *adj;    // फंक्शन की घोषणा    void fillOrder(int n, bool visited[], stack<int> &Stack);    void DFS(int n, bool visited[]);    public:       G(int N); // कंस्ट्रक्टर       void addEd(int v, int w);       int print();       G getTranspose(); }; G::G(int m) {    this->m = m;    adj = new list<int> [m]; } void G::DFS(int n, bool visited[]) {    visited[n] = true; // वर्तमान नोड को विज़िटेड मार्क करें और प्रिंट करें    cout << n << " ";    list<int>::iterator i;    // इस वर्टेक्स से आसन्न सभी वर्टेक्स के लिए रिकर्सन करें    for (i = adj[n].begin(); i != adj[n].end(); ++i)       if (!visited[*i])          DFS(*i, visited); } G G::getTranspose() {    G g(m);    for (int n = 0; n< m; n++) {       list<int>::iterator i;       for (i = adj[n].begin(); i != adj[n].end(); ++i) {          g.adj[*i].push_back(n);       }    }    return g; } void G::addEd(int v, int w) {    adj[v].push_back(w); // w को v की सूची में जोड़ें } void G::fillOrder(int v, bool visited[], stack<int> &Stack) {    visited[v] = true; // वर्तमान नोड को विज़िटेड मार्क करें और प्रिंट करें    list<int>::iterator i;    // इस वर्टेक्स से आसन्न सभी वर्टेक्स के लिए रिकर्सन करें    for (i = adj[v].begin(); i != adj[v].end(); ++i)       if (!visited[*i])          fillOrder(*i, visited, Stack);          Stack.push(v); } int G::print() { // समाधान प्रिंट करें    stack<int> Stack;    bool *visited = new bool[m];    for (int i = 0; i < m; i++)       visited[i] = false;       for (int i = 0; i < m; i++)          if (visited[i] == false)             fillOrder(i, visited, Stack);    G graph= getTranspose(); // रिवर्स ग्राफ बनाएं    for (int i = 0; i < m; i++) // सभी वर्टेक्स को अनविज़िटेड मार्क करें       visited[i] = false;    int count = 0;    // अब स्टैक द्वारा परिभाषित क्रम में सभी वर्टेक्स प्रोसेस करें    while (Stack.empty() == false) {       int v = Stack.top();       Stack.pop(); // स्टैक से वर्टेक्स पॉप करें       if (visited[v] == false) {          graph.DFS(v, visited);          cout << endl;       }       count++;    }    return count; } int main() {    G g(5);    g.addEd(2, 1);    g.addEd(3, 2);    g.addEd(1, 0);    g.addEd(0, 3);    g.addEd(3, 1);    cout << "Following are strongly connected components    in given graph \n";    if (g.print() > 1) {       cout << "Graph is weakly connected.";    } else {       cout << "Graph is strongly connected.";    }    return 0; }

आउटपुट

Following are strongly connected components in given graph 4 0 1 2 3 Graph is weakly connected.