資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式檢查圖是否強連通
在有向圖中，如果一個元件中的每對頂點之間都存在一條路徑，則稱這些元件為強連通的。
為了解決該演算法，首先使用DFS演算法獲取每個頂點的完成時間，現在找到轉置圖的完成時間，然後根據拓撲排序以降序對頂點進行排序。
輸入：圖的鄰接矩陣。
| 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 |
輸出：以下是給定圖中的強連通分量 -
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
更新於: 2019年7月30日
329 次瀏覽
廣告