โปรแกรม C++ หาจำนวนจุดประกบในกราฟ

จุดประกบ (หรือจุดยอดจุดตัด) ในกราฟคือจุดที่เอาออก (และตัดขอบผ่านจุดยอด) ทำให้กราฟตัดการเชื่อมต่อ จุดประกบสำหรับกราฟที่ไม่ได้กำหนดทิศทางคือจุดยอดซึ่งเพิ่มจำนวนองค์ประกอบที่เชื่อมต่อ

อัลกอริทึม

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 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;
}

ผลลัพธ์

Articulation points in first graph
0 2