Chương trình C ++ để tìm số cạnh tối thiểu cần cắt để làm cho đồ thị bị ngắt kết nối

Trong chương trình này, chúng ta cần tìm Khả năng kết nối cạnh của Đồ thị. Một kết nối cạnh của một biểu đồ của đồ thị có nghĩa là nó là một cầu nối, việc loại bỏ nó, đồ thị sẽ bị ngắt kết nối. Số lượng các thành phần được kết nối tăng lên khi loại bỏ cầu nối trong một biểu đồ vô hướng bị ngắt kết nối.

Hàm và mã giả

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

Chức năng và mã giả của Con ()

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

Ví dụ

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

Đầu ra

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