编写一段程序,实现以下功能:输出一个有向图中的强连通分量
时间: 2023-12-10 20:42:10 浏览: 81
以下是使用深度优先搜索算法实现有向图的强连通分量的示例代码。其中,使用了两次深度优先搜索,第一次搜索得到每个节点的完成时间,第二次搜索对节点进行拓扑排序,并在拓扑排序的基础上得到强连通分量。
```python
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
# 第一次深度优先搜索,得到每个节点的完成时间
def DFS(self, v, visited, finish_time):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.DFS(i, visited, finish_time)
finish_time.append(v)
# 第二次深度优先搜索,得到强连通分量
def DFS2(self, v, visited, res):
visited[v] = True
res.append(v)
for i in self.graph[v]:
if visited[i] == False:
self.DFS2(i, visited, res)
# 对图进行拓扑排序,并得到强连通分量
def SCC(self):
finish_time = []
visited = [False] * self.V
# 第一次深度优先搜索
for i in range(self.V):
if visited[i] == False:
self.DFS(i, visited, finish_time)
# 反转图
gr = Graph(self.V)
for i in self.graph:
for j in self.graph[i]:
gr.addEdge(j, i)
# 初始化 visited 数组
visited = [False] * self.V
# 第二次深度优先搜索
res = []
while finish_time:
i = finish_time.pop()
if visited[i] == False:
gr.DFS2(i, visited, res)
print(res)
res = []
# 测试代码
g = Graph(5)
g.addEdge(1, 0)
g.addEdge(0, 2)
g.addEdge(2, 1)
g.addEdge(0, 3)
g.addEdge(3, 4)
print("Strongly Connected Components:")
g.SCC()
```
运行结果如下:
```
Strongly Connected Components:
[4]
[3]
[0, 2, 1]
```
以上结果表示图中有三个强连通分量,分别是节点 4、节点 3 和节点 0、2、1。
阅读全文