सी ++ प्रोग्राम एक ग्राफ के वर्टेक्स कनेक्टिविटी को खोजने के लिए

एक ग्राफ की वर्टेक्स कनेक्टिविटी को खोजने के लिए हमें उस ग्राफ के आर्टिक्यूलेशन पॉइंट्स का पता लगाना होगा। ग्राफ़ में आर्टिक्यूलेशन पॉइंट (या कट वर्टिस) एक बिंदु है यदि इसे हटा दिया जाता है (और इसके माध्यम से किनारों) ग्राफ़ को डिस्कनेक्ट करता है। डिस्कनेक्ट किए गए अप्रत्यक्ष ग्राफ़ के लिए एक अभिव्यक्ति बिंदु, एक शीर्ष हटाने वाला है जो कनेक्टेड घटकों की संख्या को बढ़ाता है।

एल्गोरिदम

Begin
   We use dfs here to find articulation point:
   In DFS, a vertex w is articulation point if one of the following two conditions is satisfied.
   1) w is root of DFS tree and it has at least two children.
   2) w is not root of DFS tree and it has a child x such that no
   vertex in subtree rooted with w has a back edge to one of the ancestors of w in the tree.
End

उदाहरण

#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
   int n;
   list<int> *adj;
   //declaration of functions
   void APT(int v, bool visited[], int dis[], int low[],
   int par[], bool ap[]);
   public:
      G(int n); //constructor
      void addEd(int w, int x);
      void AP();
};
G::G(int n) {
   this->n = n;
   adj = new list<int>[n];
}
//add edges to the graph
void G::addEd(int w, int x) {
   adj[x].push_back(w); //add u to v's list
   adj[w].push_back(x); //add v to u's list
}
void G::APT(int w, bool visited[], int dis[], int low[], int
par[], bool ap[]) {
   static int t=0;
   int child = 0; //initialize child count of dfs tree is 0.
   //mark current node as visited
   visited[w] = true;
   dis[w] = low[w] = ++t;
   list<int>::iterator i;
   //Go through all adjacent vertices
   for (i = adj[w].begin(); i != adj[w].end(); ++i) {
      int x = *i; //x is current adjacent
      if (!visited[x]) {
         child++;
         par[x] = w;
         APT(x, visited, dis, low, par, ap);
         low[w] = min(low[w], low[x]);
         // w is an articulation point in following cases :
         // w is root of DFS tree and has two or more children.
         if (par[w] == N && child> 1)
            ap[w] = true;
         // If w is not root and low value of one of its child is more than discovery value of w.
         if (par[w] != N && low[x] >= dis[w])
            ap[w] = true;
      }
      else if (x != par[w]) //update low value
      low[w] = min(low[w], dis[x]);
   }
}
void G::AP() {
   // Mark all the vertices as unvisited
   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;
   }
   // Call the APT() function to find articulation points in DFS tree rooted with vertex 'i'
   for (int i = 0; i < n; i++)
      if (visited[i] == false)
         APT(i, visited, dis, low, par, ap);
   //print the articulation points
   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