資料結構
網路
關係資料庫管理系統
作業系統
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 千次以上瀏覽
廣告