그래프의 정점 연결성을 찾는 C++ 프로그램

그래프의 정점 연결성을 찾으려면 해당 그래프의 Articulation Points를 찾아야 합니다. 그래프의 Articulation Points(또는 Cut Vertex)는 이를 제거하면(그리고 이를 통과하는 모서리) 그래프의 연결이 끊어지면 점이 됩니다. 연결되지 않은 무방향 그래프의 접합점은 연결된 구성 요소의 수를 증가시키는 정점 제거입니다.

알고리즘

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