Chương trình C ++ để tìm số điểm khớp trong một đồ thị

Các điểm khớp nối (hoặc các điểm cắt) trong một đồ thị là một điểm mà nó loại bỏ nó (và các cạnh qua nó) sẽ ngắt kết nối đồ thị. Một điểm khớp nối cho một đồ thị vô hướng bị ngắt kết nối, là một điểm loại bỏ đỉnh làm tăng số lượng các thành phần được kết nối.

Thuật toán

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

Ví dụ

#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 chilren.
         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;
}

Đầu ra

Articulation points in first graph
0 2