इस प्रोग्राम में हमें ग्राफ की एज कनेक्टिविटी खोजने की आवश्यकता है। ग्राफ की एज कनेक्टिविटी का अर्थ है कि यह एक ब्रिज है, इसे हटाने पर ग्राफ डिस्कनेक्ट हो जाएगा। डिस्कनेक्टेड अनडायरेक्टेड ग्राफ में ब्रिज को हटाने पर कनेक्टेड कंपोनेंट्स की संख्या बढ़ जाती है।
फंक्शन और छद्मकोड:
Begin Function connections() कनेक्शन खोजने के लिए एक रिकर्सिव फंक्शन है: A) वर्तमान नोड को अनविज़िटेड मार्क करें। B) समय और लो वैल्यू इनिशियलाइज़ करें C) इससे आसन्न सभी वर्टेक्स से गुजरें D) जांचें कि क्या x के साथ रूटेड सबट्री का w के पूर्वजों में से एक से कनेक्शन है। यदि x के तहत सबट्री से पहुंच योग्य सबसे निचला वर्टेक्स DFS ट्री में u से नीचे है, तो w-x का कनेक्शन है। E) पैरेंट फंक्शन कॉल के लिए w के लो वैल्यू को अपडेट करें। 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); //u की सूची में v जोड़ें adj[w].push_back(x); //v की सूची में u जोड़ें } 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
