scc算法 python
时间: 2023-10-15 14:31:09 浏览: 46
SCC (Strongly Connected Components) 算法是一种用于寻找有向图中强连通分量的算法。下面是一个使用 Python 实现 SCC 算法的例子:
```python
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list) # 使用 defaultdict 创建邻接表
self.V = vertices
def addEdge(self, u, v):
self.graph[u].append(v) # 将边添加到邻接表中
# 深度优先搜索函数
def DFS(self, v, visited, stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.DFS(i, visited, stack)
stack.append(v)
# 反转图的边
def reverseGraph(self):
g = Graph(self.V)
for i in self.graph:
for j in self.graph[i]:
g.addEdge(j, i)
return g
# 寻找强连通分量
def findSCCs(self):
stack = []
visited = [False] * (self.V)
# 第一次 DFS,将顶点按照结束时间压入栈中
for i in range(self.V):
if visited[i] == False:
self.DFS(i, visited, stack)
# 反转图的边
gr = self.reverseGraph()
visited = [False] * (self.V)
scc_list = []
# 从栈中取出顶点,进行第二次 DFS
while stack:
v = stack.pop()
if visited[v] == False:
scc = []
gr.DFS(v, visited, scc)
scc_list.append(scc)
return scc_list
# 测试代码
g = Graph(5)
g.addEdge(1, 0)
g.addEdge(0, 2)
g.addEdge(2, 1)
g.addEdge(0, 3)
g.addEdge(3, 4)
print("强连通分量为:")
scc_list = g.findSCCs()
for scc in scc_list:
print(scc)
```
以上代码实现了 SCC 算法,通过构建图并使用深度优先搜索来查找强连通分量。测试代码中的图是一个简单的有向图,输出结果会显示图中的强连通分量。运行代码后,输出应为:
```
强连通分量为:
[3, 4]
[0, 2, 1]
```
这表示图中有两个强连通分量,一个包含节点 3 和 4,另一个包含节点 0、2 和 1。