इस प्रोग्राम में ग्राफ में मैक्सिमम कट खोजने के लिए, हमें ग्राफ की एज कनेक्टिविटी (Edge Connectivity) ज्ञात करनी होती है। एक ग्राफ की एज कनेक्टिविटी का अर्थ है एक ब्रिज (Bridge), जिसे हटाने पर ग्राफ डिस्कनेक्ट हो जाता है। एक डिस्कनेक्टेड अनडायरेक्टेड ग्राफ में ब्रिज को हटाने पर कनेक्टेड कॉम्पोनेंट्स की संख्या बढ़ जाती है।
फंक्शन और स्यूडोकोड
Begin
Function connections() कनेक्शन खोजने के लिए एक रिकर्सिव फंक्शन है:
A) वर्तमान नोड को अनविज़िटेड मार्क करें।
B) टाइम और low मान इनिशियलाइज़ करें।
C) इस वर्टेक्स से आसन्न सभी वर्टेक्स के माध्यम से जाएं।
D) जांचें कि क्या x में रूटेड सबट्री का w के पूर्वजों में से किसी एक से कनेक्शन है। यदि x के नीचे सबट्री से पहुंचने योग्य सबसे निचला वर्टेक्स, DFS ट्री में u से नीचे है, तो w-x का एक कनेक्शन है।
E) पैरेंट फंक्शन कॉल के लिए w का low मान अपडेट करें।
End
Begin
Function Con() जो connections() का उपयोग करता है:
A) सभी वर्टेक्स को अनविज़िटेड मार्क करें।
B) पैरेंट, विज़िटेड, और कनेक्शन इनिशियलाइज़ करें।
C) ग्राफ में एज के बीच कनेक्शन प्रिंट करें।
End
उदाहरण
#include<iostream> #include <list> #define N -1 using namespace std; class G { // फंक्शन की घोषणा int n; list<int> *adj; void connections(int n, bool visited[], int disc[], int low[], int par[]); public: G(int n); // कंस्ट्रक्टर void addEd(int w, int x); void Con(); }; G::G(int n) { this->n= n; adj = new list<int> [n]; } // ग्राफ में एज जोड़ें void G::addEd(int w, int x) { adj[x].push_back(w); // v की सूची में u जोड़ें adj[w].push_back(x); // u की सूची में v जोड़ें } void G::connections(int w, bool visited[], int dis[], int low[], int par[]) { static int t = 0; // वर्तमान नोड को विज़िटेड मार्क करें visited[w] = true; dis[w] = low[w] = ++t; // सभी आसन्न वर्टेक्स के माध्यम से जाएं list<int>::iterator i; for (i = adj[w].begin(); i != adj[w].end(); ++i) { int x = *i; // x वर्तमान आसन्न है if (!visited[x]) { par[x] = w; connections(x, visited, dis, low, par); low[w] = min(low[w], low[x]); // यदि x के नीचे सबट्री से पहुंचने योग्य सबसे निचला वर्टेक्स, DFS ट्री में w से नीचे है, तो w-x एक कनेक्शन है if (low[x] > dis[w]) cout << w << " " << x << endl; } else if (x != par[w]) low[w] = min(low[w], dis[x]); } } void G::Con() { // सभी वर्टेक्स को अनविज़िटेड मार्क करें bool *visited = new bool[n]; int *dis = new int[n]; int *low = new int[n]; int *par = new int[n]; for (int i = 0; i < n; i++) { par[i] = N; visited[i] = false; } // एज कनेक्शन खोजने के लिए connections() फंक्शन कॉल करें for (int i = 0; i < n; i++) if (visited[i] == false) connections(i, visited, dis, low, par); } int main() { cout << "\nConnections in first graph \n"; G g1(5); g1.addEd(1, 2); g1.addEd(3, 2); g1.addEd(2, 1); g1.addEd(0, 1); g1.addEd(1, 4); g1.Con(); return 0; }
आउटपुट
Connections in first graph 2 3 1 2 1 4 0 1
