資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中檢查圖是否強連通 - 集合1（使用DFS的Kosaraju演算法）
假設我們有一個圖。我們必須使用Kosaraju演算法檢查該圖是否強連通。如果任何兩個頂點之間都有路徑，則稱該圖是強連通的。無向圖是強連通圖。
一些無向圖可能是連通的，但不是強連通的。這是一個強連通圖的例子。
這是一個連通的但不是強連通圖的例子。
在這裡，我們將看到如何使用Kosaraju演算法的以下步驟來檢查圖是否強連通。
步驟−
將所有節點標記為未訪問。
從任意頂點u開始DFS遍歷。如果DFS未能訪問所有節點，則返回false。
反轉圖的所有邊。
再次將所有頂點設定為未訪問節點。
從頂點u開始DFS遍歷。如果DFS未能訪問所有節點，則返回false；否則返回true。
示例
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V;
list<int> *adj;
void dfs(int v, bool visited[]);
public:
Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
~Graph() {
delete [] adj;
}
void addEdge(int v, int w);
bool isStronglyConnected();
Graph reverseArc();
};
void Graph::dfs(int v, bool visited[]) {
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
dfs(*i, visited);
}
Graph Graph::reverseArc() {
Graph graph(V);
for (int v = 0; v < V; v++) {
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
graph.adj[*i].push_back(v);
}
return graph;
}
void Graph::addEdge(int u, int v) {
adj[u].push_back(v);
}
bool Graph::isStronglyConnected() {
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
dfs(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
Graph graph = reverseArc();
for(int i = 0; i < V; i++)
visited[i] = false;
graph.dfs(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
int main() {
Graph graph(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(2, 4);
graph.addEdge(4, 2);
graph.isStronglyConnected()? cout << "This is strongly connected" : cout << "This is not strongly connected";
}輸出
This is strongly connected
更新於：2019年10月22日
230 次檢視
廣告