python 利用trajan算法求给定邻接矩阵的强连通图,输入数据的邻接矩阵
时间: 2024-01-10 19:28:44 浏览: 28
Trajan算法是一种用于求解有向图的强连通分量的算法。下面是使用Trajan算法求给定邻接矩阵的强连通图的Python示例代码:
```python
def tarjan(graph):
n = len(graph)
index_counter = [0]
index = [-1] * n
lowlink = [-1] * n
onStack = [False] * n
stack = []
result = []
def strongconnect(v):
index[v] = index_counter[0]
lowlink[v] = index_counter[0]
index_counter[0] += 1
stack.append(v)
onStack[v] = True
for w in range(n):
if graph[v][w] == 1:
if index[w] == -1:
strongconnect(w)
lowlink[v] = min(lowlink[v], lowlink[w])
elif onStack[w]:
lowlink[v] = min(lowlink[v], index[w])
if lowlink[v] == index[v]:
scc = []
while True:
w = stack.pop()
onStack[w] = False
scc.append(w)
if w == v:
break
result.append(scc)
for v in range(n):
if index[v] == -1:
strongconnect(v)
return result
# 示例用法
adj_matrix = [
[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0]
]
result = tarjan(adj_matrix)
print("强连通分量为:")
for scc in result:
print(scc)
```
在示例中,我们首先定义了 `tarjan` 函数来实现Trajan算法。该函数接受邻接矩阵作为输入,并返回强连通分量的列表。然后,我们使用示例中的邻接矩阵调用 `tarjan` 函数,并打印出强连通分量。
请注意,输入的邻接矩阵应该是一个二维列表,其中1表示存在边,0表示不存在边。输出结果将显示强连通分量的顶点集合。