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

C++ में ग्राफ दृढ़ता से जुड़ा (Strongly Connected) है या नहीं जांचें - कोसराजू एल्गोरिदम


दृढ़ता से जुड़ा ग्राफ

एक निर्देशित ग्राफ दृढ़ता से जुड़ा है यदि किन्हीं दो शीर्षों के बीच दोनों दिशाओं में पथ मौजूद हो।

कोसराजू एल्गोरिदम (DFS आधारित)

  1. सभी नोड्स को अनविजिटेड मार्क करें
  2. किसी भी शीर्ष से DFS करें। यदि सभी नोड्स विजिट नहीं हुए → false
  3. सभी एज उलट दें (ट्रांसपोज ग्राफ)
  4. फिर से सभी अनविजिटेड मार्क करें
  5. उसी शीर्ष से DFS करें। यदि सभी विजिट नहीं हुए → false
  6. अन्यथा → true

उदाहरण कोड

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class Graph {
    int V;
    list* adj;
    void dfs(int v, bool visited[]);
public:
    Graph(int V) { this->V = V; adj = new list[V]; }
    ~Graph() { delete[] adj; }
    void addEdge(int v, int w) { adj[v].push_back(w); }
    bool isStronglyConnected();
    Graph reverseArc();
};

void Graph::dfs(int v, bool visited[]) {
    visited[v] = true;
    for (int u : adj[v])
        if (!visited[u]) dfs(u, visited);
}

Graph Graph::reverseArc() {
    Graph g(V);
    for (int v = 0; v < V; v++)
        for (int u : adj[v])
            g.adj[u].push_back(v);
    return g;
}

bool Graph::isStronglyConnected() {
    bool visited[V];
    fill(visited, visited+V, false);
    dfs(0, visited);
    for (int i = 0; i < V; i++) if (!visited[i]) return false;
    
    Graph gr = reverseArc();
    fill(visited, visited+V, false);
    gr.dfs(0, visited);
    for (int i = 0; i < V; i++) if (!visited[i]) return false;
    
    return true;
}

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 0);
    g.addEdge(2, 4);
    g.addEdge(4, 2);
    
    g.isStronglyConnected() ? cout << "This is strongly connected"
                            : cout << "This is not strongly connected";
    return 0;
}

आउटपुट

This is strongly connected
  1. C++ प्रोग्राम: DFS का उपयोग करके अनडायरेक्टेड ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: DFS का उपयोग करके अनडायरेक्टेड ग्राफ की कनेक्टिविटी जांचना

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

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

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

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

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