C++程序检查图是否强连通

在有向图中，如果一个组件中的每对顶点之间都存在一条路径，则称这些组件为强连通的。

为了解决该算法，首先使用DFS算法获取每个顶点的完成时间，现在找到转置图的完成时间，然后根据拓扑排序以降序对顶点进行排序。

输入：图的邻接矩阵。

输出：以下是给定图中的强连通分量 -

0 1 2
3
4

算法

traverse(graph, start, visited)

输入：将被遍历的图，起始顶点以及已访问节点的标志。

节点。

输出：使用DFS技术遍历每个节点并显示节点。

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, visited, stack)

输入 - 起始节点，已访问顶点的标志，栈。

输出 - 在排序图时填充栈。

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(graph)

输入 - 给定的图。

输出 - 所有强连通分量。

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

示例代码

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

输出

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

Krantik Chavan

更新于: 2019年7月30日

329 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习