ग्राफ में आर्टिकुलेशन पॉइंट्स (या कट वर्टेक्स) एक पॉइंट है यदि इसे हटाने पर (और इसके माध्यम से एज) ग्राफ डिस्कनेक्ट हो जाता है। एक डिस्कनेक्टेड अनडायरेक्टेड ग्राफ के लिए एक आर्टिकुलेशन पॉइंट एक वर्टेक्स है जिसे हटाने पर कनेक्टेड कंपोनेंट्स की संख्या बढ़ जाती है।
एल्गोरिदम
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); //u की सूची में v जोड़ें adj[w].push_back(x); //v की सूची में u जोड़ें } 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 रूट नहीं है और इसके एक बच्चे का लो वैल्यू w के डिस्कवरी वैल्यू से अधिक या बराबर है। if (par[w] != N && low[x] >= dis[w]) ap[w] = true; } else if (x != par[w]) //लो वैल्यू अपडेट करें 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; } // APT() फंक्शन कॉल करें ताकि वर्टेक्स 'i' के साथ रूटेड DFS ट्री में आर्टिकुलेशन पॉइंट खोजे जा सकें 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
