数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学强连通图
在一个有向图中，如果一个连通分量中每对顶点之间都有路径，则称该图是强连通图。
要解决此算法，首先使用深度优先搜索 (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: Following are strongly connected components in given graph: 0 1 2 3 4
算法
traverse(graph, start, visited)
输入：将要遍历的图、起始顶点和已访问节点的标记。
输出：使用深度优先搜索技术遍历每个节点并显示节点。
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
更新日期：2020 年 6 月 16 日
4 千次以上浏览
广告