ग्राफ की वर्टेक्स कनेक्टिविटी ज्ञात करने के लिए हमें उस ग्राफ के आर्टिकुलेशन पॉइंट्स (Articulation Points) ढूंढने होते हैं। एक ग्राफ में आर्टिकुलेशन पॉइंट्स (या कट वर्टेक्स) वे शीर्ष होते हैं जिन्हें हटाने से (और उससे जुड़े एज भी) ग्राफ डिस्कनेक्ट हो जाता है। एक डिस्कनेक्टेड अनडायरेक्टेड ग्राफ के लिए, एक आर्टिकुलेशन पॉइंट वह शीर्ष होता है जिसे हटाने पर कनेक्टेड कॉम्पोनेंट्स की संख्या बढ़ जाती है।
एल्गोरिदम
Begin
हम यहां DFS का उपयोग आर्टिकुलेशन पॉइंट खोजने के लिए करते हैं:
DFS में, एक शीर्ष w आर्टिकुलेशन पॉइंट है यदि निम्नलिखित दो शर्तों में से कोई एक पूरी होती है।
1) w DFS ट्री का रूट है और इसके कम से कम दो बच्चे हैं।
2) w DFS ट्री का रूट नहीं है और इसका एक बच्चा x ऐसा है कि w में रूटेड सबट्री का कोई भी वर्टेक्स, ट्री में w के पूर्वजों में से किसी एक से बैक एज द्वारा जुड़ा नहीं है।
End
उदाहरण
#include<iostream> #include <list> #define N -1 using namespace std; class G { int n; list<int> *adj; // फंक्शन की घोषणा void APT(int v, bool visited[], int dis[], int low[], int par[], bool ap[]); public: G(int n); // कंस्ट्रक्टर void addEd(int w, int x); void AP(); }; 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::APT(int w, bool visited[], int dis[], int low[], int par[], bool ap[]) { static int t=0; int child = 0; // DFS ट्री के चाइल्ड काउंट को 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]) { child++; par[x] = w; APT(x, visited, dis, low, par, ap); low[w] = min(low[w], low[x]); // w निम्नलिखित मामलों में आर्टिकुलेशन पॉइंट है: // w DFS ट्री का रूट है और इसके दो या अधिक बच्चे हैं। if (par[w] == N && child> 1) ap[w] = true; // यदि w रूट नहीं है और इसके किसी बच्चे का low मान w के डिस्कवरी मान से अधिक या बराबर है। if (par[w] != N && low[x] >= dis[w]) ap[w] = true; } else if (x != par[w]) // low मान अपडेट करें low[w] = min(low[w], dis[x]); } } void G::AP() { // सभी वर्टेक्स को अनविज़िटेड मार्क करें bool *visited = new bool[n]; int *dis = new int[n]; int *low = new int[n]; int *par = new int[n]; bool *ap = new bool[n]; for (int i = 0; i < n; i++) { par[i] = N; visited[i] = false; ap[i] = false; } // वर्टेक्स 'i' से रूटेड DFS ट्री में आर्टिकुलेशन पॉइंट खोजने के लिए APT() फंक्शन कॉल करें for (int i = 0; i < n; i++) if (visited[i] == false) APT(i, visited, dis, low, par, ap); // आर्टिकुलेशन पॉइंट्स प्रिंट करें for (int i = 0; i < n; i++) if (ap[i] == true) cout << i << " "; } int main() { cout << "\nArticulation points in first graph \n"; G g1(5); g1.addEd(1, 2); g1.addEd(3, 1); g1.addEd(0, 2); g1.addEd(2, 3); g1.addEd(0, 4); g1.AP(); return 0; }
आउटपुट
Articulation points in first graph 0 2
