强连通分量
提示
- 强连通分量定义：强连通分量是有向图中的一部分，其中任意两个顶点都通过路径相互可达。
- Kosaraju算法：这是一种用于寻找有向图中所有强连通分量的算法，包括三个步骤：对整个图进行深度优先搜索，反转原始图，再次对反转图执行深度优先搜索。
- 应用场景：强连通分量的概念应用于车辆路线规划、地图制作和模型检查等领域。
强连通分量是有向图的一部分，在这部分中，每个顶点都可以通过路径到达另一个顶点。它只适用于有向图。
例如：
让我们看下面的图。
上图的强连 通分量是：
你可以观察到，在第一个强连通分量中，每个顶点都可以通过有向路径到达另一个顶点。
这些分量可以使用Kosaraju 算法找到。
Kosaraju 算法
Kosaraju 算法基于深度优先搜索算法，实施两次。
涉及三个步骤。
- 对整个图执行深度优先搜索。
让我们从顶点-0开始，访问它的所有子顶点，并将访问过的顶点标记为已完成。如果一个顶点指向已访问过的顶点，那么将这个顶点推入栈中。
例如：从顶点-0开始，依次前往顶点-1、顶点-2，然后到顶点-3。顶点-3指向已经访问过的顶点-0，所以将源顶点（即顶点-3）推入栈中。
回到前一个顶点（顶点-2）并访问其子顶点，即顶点-4、顶点-5、顶点-6和顶点-7。由于顶点-7无处可去，将其推入栈中。
回到前一个顶点（顶点-6）并访问其子顶点。但是，它的所有子顶点都已被访问，所以将其推入栈中。
类似地，创建最终栈。
-
反转原始图。
-
对反转的图执行深度优先搜索。
从栈顶顶点开始。遍历其所有子顶点。一旦到达已访问的顶点，就形成一个强连通分量。
例如：从栈中弹出顶点-0。从顶点-0开始，遍历其子顶点（依次为顶点-0、顶点-1、顶点-2、顶点-3）并将它们标记为已访问。顶点-3的子顶点已被访问，所以这些访问过的顶点形成一个强连通分量。
回到栈并弹出顶部顶点，如果已访问。否则，从栈中选择顶部顶点并按上述方式遍历其子顶点。
- 因此，强连通分量为：
Python、Java、C++ 示例
# Python 中使用 Kosaraju 算法找到强连通分量
from collections import defaultdict
class Graph:
def __init__(self, vertex):
self.V = vertex
self.graph = defaultdict(list)
# 向图中添加边
def add_edge(self, s, d):
self.graph[s].append(d)
# dfs
def dfs(self, d, visited_vertex):
visited_vertex[d] = True
print(d, end='')
for i in self.graph[d]:
if not visited_vertex[i]:
self.dfs(i, visited_vertex)
def fill_order(self, d, visited_vertex, stack):
visited_vertex[d] = True
for i in self.graph[d]:
if not visited_vertex[i]:
self.fill_order(i, visited_vertex, stack)
stack = stack.append(d)
# 转置矩阵
def transpose(self):
g = Graph(self.V)
for i in self.graph:
for j in self.graph[i]:
g.add_edge(j, i)
return g
# 打印强连通分量
def print_scc(self):
stack = []
visited_vertex = [False] * (self.V)
for i in range(self.V):
if not visited_vertex[i]:
self.fill_order(i, visited_vertex, stack)
gr = self.transpose()
visited_vertex = [False] * (self.V)
while stack:
i = stack.pop()
if not visited_vertex[i]:
gr.dfs(i, visited_vertex)
print("")
g = Graph(8)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.add_edge(3, 0)
g.add_edge(4, 5)
g.add_edge(5, 6)
g.add_edge(6, 4)
g.add_edge(6, 7)
print("强连通分量:")
g.print_scc()
// Java 中使用 Kosaraju 算法寻找强连通分量
import java.util.*;
import java.util.LinkedList;
class Graph {
private int V; // 顶点的数量
private LinkedList<Integer> adj[]; // 邻接表
// 创建一个图
Graph(int s) {
V = s;
adj = new LinkedList[s];
for (int i = 0; i < s; ++i)
adj[i] = new LinkedList();
}
// 添加边
void addEdge(int s, int d) {
adj[s].add(d);
}
// 深度优先搜索
void DFSUtil(int s, boolean visitedVertices[]) {
visitedVertices[s] = true;
System.out.print(s + " ");
int n;
Iterator<Integer> i = adj[s].iterator();
while (i.hasNext()) {
n = i.next();
if (!visitedVertices[n])
DFSUtil(n, visitedVertices);
}
}
// 转置图
Graph Transpose() {
Graph g = new Graph(V);
for (int s = 0; s < V; s++) {
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext())
g.adj[i.next()].add(s);
}
return g;
}
void fillOrder(int s, boolean visitedVertices[], Stack stack) {
visitedVertices[s] = true;
Iterator<Integer> i = adj[s].iterator();
while (i.hasNext()) {
int n = i.next();
if (!visitedVertices[n])
fillOrder(n, visitedVertices, stack);
}
stack.push(new Integer(s));
}
// 打印强连通分量
void printSCC() {
Stack stack = new Stack();
boolean visitedVertices[] = new boolean[V];
for (int i = 0; i < V; i++)
visitedVertices[i] = false;
for (int i = 0; i < V; i++)
if (visitedVertices[i] == false)
fillOrder(i, visitedVertices, stack);
Graph gr = Transpose();
for (int i = 0; i < V; i++)
visitedVertices[i] = false;
while (stack.empty() == false) {
int s = (int) stack.pop();
if (visitedVertices[s] == false) {
gr.DFSUtil(s, visitedVertices);
System.out.println();
}
}
}
public static void main(String args[]) {
Graph g = new Graph(8);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 0);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.addEdge(6, 4);
g.addEdge(6, 7);
System.out.println("强连通分量:");
g.printSCC();
}
}
// C++ 中使用 Kosaraju 算法寻找强连通分量
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V; // 顶点的数量
list<int> *adj; // 邻接表
void fillOrder(int s, bool visitedV[], stack<int> &Stack);
void DFS(int s, bool visitedV[]); // 深度优先搜索
public:
Graph(int V);
void addEdge(int s, int d); // 添加边
void printSCC(); // 打印强连通分量
Graph transpose(); // 转置图
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
// 深度优先搜索
void Graph::DFS(int s, bool visitedV[]) {
visitedV[s] = true;
cout << s << " ";
list<int>::iterator i;
for (i = adj[s].begin(); i != adj[s].end(); ++i)
if (!visitedV[*i])
DFS(*i, visitedV);
}
// 转置图
Graph Graph::transpose() {
Graph g(V);
for (int s = 0; s < V; s++) {
list<int>::iterator i;
for (i = adj[s].begin(); i != adj[s].end(); ++i) {
g.adj[*i].push_back(s);
}
}
return g;
}
// 添加边
void Graph::addEdge(int s, int d) {
adj[s].push_back(d);
}
void Graph::fillOrder(int s, bool visitedV[], stack<int> &Stack) {
visitedV[s] = true;
list<int>::iterator i;
for (i = adj[s].begin(); i != adj[s].end(); ++i)
if (!visitedV[*i])
fillOrder(*i, visitedV, Stack);
Stack.push(s);
}
// 打印强连通分量
void Graph::printSCC() {
stack<int> Stack;
bool *visitedV = new bool[V];
for (int i = 0; i < V; i++)
visitedV[i] = false;
for (int i = 0; i < V; i++)
if (visitedV[i] == false)
fillOrder(i, visitedV, Stack);
Graph gr = transpose();
for (int i = 0; i < V; i++)
visitedV[i] = false;
while (Stack.empty() == false) {
int s = Stack.top();
Stack.pop();
if (visitedV[s] == false) {
gr.DFS(s, visitedV);
cout << endl;
}
}
}
int main() {
Graph g(8);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 0);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.addEdge(6, 4);
g.addEdge(6, 7);
cout << "强连通分量:\n";
g.printSCC();
}
Kosaraju 算法的复杂度
Kosaraju 算法的运行时间是线性的，即 O(V+E)。
强连通分量的应用
- 车辆路线规划应用
- 地图
- 正式验证中的模型检查