একটি গ্রাফের প্রান্ত সংযোগ খুঁজে পেতে C++ প্রোগ্রাম

এই প্রোগ্রামে আমাদের একটি গ্রাফের এজ কানেক্টিভিটি খুঁজে বের করতে হবে। একটি গ্রাফের একটি গ্রাফের একটি প্রান্ত সংযোগ মানে এটি একটি সেতু, এটিকে সরিয়ে দিলে গ্রাফটি সংযোগ বিচ্ছিন্ন হয়ে যাবে। সংযোগ বিচ্ছিন্ন অনির্দেশিত গ্রাফে সেতু অপসারণের সাথে সংযুক্ত উপাদানের সংখ্যা বৃদ্ধি পায়।

ফাংশন এবং সিউডোকোড:

Begin
   Function connections() is a recursive function to find out the connections:
   A) Mark the current node un visited.
   B) Initialize time and low value
   C) Go through all vertices adjacent to this
   D) Check if the subtree rooted with x has a connection to one of the ancestors of w. If the lowest vertex reachable from subtree under x is below u in DFS tree, then w-x has a connection.
   E) Update low value of w for parent function calls.
End
Begin
   Function Con() that uses connections():
   A) Mark all the vertices as unvisited.
   B) Initialize par and visited, and connections.
   C) Print the connections between the edges in the graph.
End

উদাহরণ

#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
   //declaration of functions
   int n;
   list<int> *adj;
   void connections(int n, bool visited[], int disc[], int low[],
   int par[]);
   public:
      G(int n); //constructor
      void addEd(int w, int x);
      void Con();
};
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::connections(int w, bool visited[], int dis[], int low[], int par[]) {
   static int t = 0;
   //mark current node as visited
   visited[w] = true;
   dis[w] = low[w] = ++t;
   //Go through all adjacent vertices
   list<int>::iterator i;
   for (i = adj[w].begin(); i != adj[w].end(); ++i) {
      int x = *i; //x is current adjacent
      if (!visited[x]) {
         par[x] = w;
         connections(x, visited, dis, low, par);
         low[w] = min(low[w], low[x]);
         // If the lowest vertex reachable from subtree under x is below w in DFS tree, then w-x is a connection
         if (low[x] > dis[w])
            cout << w << " " << x << endl;
      } else if (x != par[w])
         low[w] = min(low[w], dis[x]);
   }
}
void G::Con() {
   // 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];
   for (int i = 0; i < n; i++) {
      par[i] = N;
      visited[i] = false;
   }
   //call the function connections() to find edge connections
   for (int i = 0; i < n; i++)
      if (visited[i] == false)
         connections(i, visited, dis, low, par);
}
int main() {
   cout << "\nConnections in first graph \n";
   G g1(5);
   g1.addEd(1, 2);
   g1.addEd(3, 2);
   g1.addEd(2, 1);
   g1.addEd(0, 1);
   g1.addEd(1, 4);
   g1.Con();
   return 0;
}

আউটপুট

Connections in first graph
2 3
1 2
1 4
0 1