दिए गए डायरेक्टेड ग्राफ के लिए वीकली (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.
