Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: डायरेक्टेड ग्राफ के लिए वीकली कनेक्टेड या स्ट्रॉन्गली कनेक्टेड जांचें


दिए गए डायरेक्टेड ग्राफ के लिए वीकली या स्ट्रॉन्गली कनेक्टेड का पता 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); //v की सूची में w जोड़ें } 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.

  1. C++ प्रोग्राम: जांचें कि क्या एक निर्देशित ग्राफ में यूलरियन चक्र है C++ प्रोग्राम: जांचें कि क्या एक निर्देशित ग्राफ में यूलरियन चक्र है

    यूलर चक्र/सर्किट एक पथ है; जिसके द्वारा हम प्रत्येक एज को ठीक एक बार देख सकते हैं। हम एक ही वर्टेक्स का कई बार उपयोग कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक वर्टेक्स उस पथ के अंतिम वर्टेक्स से भी जुड़ा होता है, तो इसे यूलर सर्किट कहा जाता है। यह जांचने के लि

  1. C++ प्रोग्राम: जांचें कि क्या एक ग्राफ दृढ़ता से जुड़ा हुआ है या नहीं C++ प्रोग्राम: जांचें कि क्या एक ग्राफ दृढ़ता से जुड़ा हुआ है या नहीं

    निर्देशित ग्राफ में घटकों को दृढ़ता से जुड़ा हुआ कहा जाता है, जब एक घटक में वर्टेक्स के प्रत्येक जोड़े के बीच एक पथ होता है। इस एल्गोरिदम को हल करने के लिए, पहले, प्रत्येक वर्टेक्स का फिनिश टाइम प्राप्त करने के लिए DFS एल्गोरिदम का उपयोग किया जाता है, अब ट्रांसपोज़्ड ग्राफ का फिनिश टाइम ढूंढें, फि

  1. C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना

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