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

इस प्रोग्राम में हमें एक ग्राफ की एज कनेक्टिविटी ढूंढनी है। एक ग्राफ की एज कनेक्टिविटी का अर्थ है यह एक ब्रिज है, इसे हटाने पर ग्राफ डिस्कनेक्ट हो जाएगा। एक डिस्कनेक्टेड अनडायरेक्टेड ग्राफ में ब्रिज को हटाने पर कनेक्टेड कंपोनेंट्स की संख्या बढ़ जाती है।

फंक्शन्स और सूडोकोड

connections() एक रिकर्सिव फंक्शन है जो कनेक्शन्स ढूंढने के लिए है:

• A) वर्तमान नोड को विजिटेड मार्क करें।
• B) टाइम और लो वैल्यू इनिशियलाइज़ करें।
• C) इस वर्टेक्स से एडजेसेंट सभी वर्टेक्सेस के माध्यम से जाएं।
• D) जांचें कि क्या x से रूटेड सबट्री का w के पूर्वजों में से किसी एक से कनेक्शन है।
• E) पैरेंट फंक्शन कॉल्स के लिए w की लो वैल्यू अपडेट करें।

C++ कार्यान्वयन

#include <iostream>
#include <list>
#define NIL -1
using namespace std;

class Graph {
    int V;
    list *adj;
    void bridgeUtil(int u, bool visited[], int disc[], int low[], int parent[]);
public:
    Graph(int V);
    void addEdge(int u, int v);
    void findBridges();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list[V];
}

void Graph::addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void Graph::bridgeUtil(int u, bool visited[], int disc[], int low[], int parent[]) {
    static int time = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            parent[v] = u;
            bridgeUtil(v, visited, disc, low, parent);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u])
                cout << u << " " << v << endl;
        } else if (v != parent[u]) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

void Graph::findBridges() {
    bool *visited = new bool[V];
    int *disc = new int[V];
    int *low = new int[V];
    int *parent = new int[V];
    
    for (int i = 0; i < V; i++) {
        parent[i] = NIL;
        visited[i] = false;
    }
    
    for (int i = 0; i < V; i++)
        if (!visited[i])
            bridgeUtil(i, visited, disc, low, parent);
}

int main() {
    cout << "\nBridges in first graph \n";
    Graph g1(5);
    g1.addEdge(1, 2);
    g1.addEdge(3, 2);
    g1.addEdge(2, 1);
    g1.addEdge(0, 1);
    g1.addEdge(1, 4);
    g1.findBridges();
    return 0;
}

आउटपुट

Bridges in first graph
2 3
1 2
1 4
0 1

व्याख्या

ये एजेस ब्रिज हैं - इन्हें हटाने से ग्राफ डिस्कनेक्ट हो जाएगा। यह टार्जन के एल्गोरिदम पर आधारित O(V+E) समाधान है।