强连通图

2023-06-21 06:30:03 259

在有向图中，当一个组件中的每对顶点之间存在路径时，就称其为强连通图。

为了解决这个算法，首先使用DFS算法得到每个顶点的完成时间，现在找到转置图的完成时间，然后通过拓扑排序对顶点进行降序排序。

输入和输出

Input:
Adjacency matrix of the graph.
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

Output:
以下是给定图中的强连通分量：
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 
#include 
#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() {    //转置图并存储到transGraph
   for(int i = 0; i&stk) {
   visited[u] = true;    //设置为节点v被访问

   for(int v = 0; v stk;
   bool vis[NODE];

   for(int i = 0; i输出结果以下是给定图中的强连通分量：
0 1 2
3
4

强连通图

输入和输出

算法

示例

热门推荐

随机推荐