Chương trình C ++ để kiểm tra xem một đồ thị có được kết nối mạnh mẽ hay không

Trong đồ thị có hướng, các thành phần được cho là liên kết chặt chẽ, khi có một đường đi giữa mỗi cặp đỉnh trong một thành phần.

Để giải thuật toán này, trước hết, thuật toán DFS được sử dụng để lấy thời gian kết thúc của mỗi đỉnh, bây giờ tìm thời gian kết thúc của đồ thị chuyển vị, sau đó các đỉnh được sắp xếp theo thứ tự giảm dần theo cách sắp xếp tôpô.

Đầu vào :Ma trận kề của biểu đồ.

Đầu ra :Sau đây là các thành phần được kết nối chặt chẽ trong biểu đồ đã cho -

0 1 2
3
4

Thuật toán

đi ngang (đồ thị, bắt đầu, đã truy cập)

Đầu vào :Biểu đồ sẽ được duyệt qua, đỉnh bắt đầu và cờ của những người đã truy cập

các nút.

Đầu ra :Đi qua từng nút trong kỹ thuật DFS và các nút hiển thị.

Begin
   mark start as visited
   for all vertices v connected with start, do
      if v is not visited, then
         traverse(graph, v, visited)
   done
End

topoSort (u, đã thăm, ngăn xếp)

Đầu vào - Nút bắt đầu, cờ cho các đỉnh đã thăm, ngăn xếp.

Đầu ra - Điền vào ngăn xếp trong khi sắp xếp đồ thị.

Begin 
   mark u as visited 
   for all node v, connected with u, do 
      if v is not visited, then 
         topoSort(v, visited, stack) 
   done 
   push u into the stack 
End

getStrongConComponents (đồ thị)

Đầu vào - Đồ thị đã cho.

Đầu ra - Tất cả các thành phần được kết nối mạnh mẽ.

Begin
   initially all nodes are unvisited
   for all vertex i in the graph, do
      if i is not visited, then
         topoSort(i, vis, stack)
   done
   make all nodes unvisited again
   transGraph := transpose of given graph
   while stack is not empty, do
      pop node from stack and take into v
      if v is not visited, then
         traverse(transGraph, v, visited)
   done
End

Mã mẫu

#include <iostream>
#include <stack>
#define NODE 5
using namespace std;
int graph[NODE][NODE]= {
   {0, 0, 1, 1, 0},
   {1, 0, 0, 0, 0},
   {0, 1, 0, 0, 0},
   {0, 0, 0, 0, 1},
   {0, 0, 0, 0, 0}};
int transGraph[NODE][NODE];
void transpose() {       //transpose the graph and store to transGraph
   for(int i = 0; i<NODE; i++)
      for(int j = 0; j<NODE; j++)
         transGraph[i][j] = graph[j][i];
}
void traverse(int g[NODE][NODE], int u, bool visited[]) {
   visited[u] = true;    //mark v as visited
   cout << u << " ";
   for(int v = 0; v<NODE; v++) {
      if(g[u][v]) {
         if(!visited[v])
            traverse(g, v, visited);
      }
   }
}
void topoSort(int u, bool visited[], stack<int> &stk) {
   visited[u] = true;     //set as the node v is visited
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]) {     //for allvertices v adjacent to u
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }
   stk.push(u);     //push starting vertex into the stack
}
void getStrongConComponents() {
   stack<int> stk;
   bool vis[NODE];
   for(int i = 0; i<NODE; i++)
      vis[i] = false;    //initially all nodes are unvisited
   for(int i = 0; i<NODE; i++)
      if(!vis[i])     //when node is not visited
         topoSort(i, vis, stk);
   for(int i = 0; i<NODE; i++)
      vis[i] = false;    //make all nodes are unvisited for traversal
   transpose();       //make reversed graph
   while(!stk.empty()) {     //when stack contains element, process in topological order
      int v = stk.top(); stk.pop();
         if(!vis[v]) {
            traverse(transGraph, v, vis);
            cout << endl;
         }
   }
}
int main() {
   cout << "Following are strongly connected components in given graph: "<<endl;
   getStrongConComponents();
}

Đầu ra

Following are strongly connected components in given graph:
0 1 2
3
4