数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
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)
输入: 要遍历的图，起始顶点和已访问节点的标志。
输出: 使用 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
更新于： 16-Jun-2020
4K+ 次浏览
广告