একটি গ্রাফে আর্টিকুলেশন পয়েন্টের সংখ্যা খুঁজে পেতে 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