数据结构
网络
关系数据库管理系统 (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 次查看
广告