python求可达矩阵
时间: 2023-08-23 21:04:47 浏览: 120
可达矩阵又称为传递闭包,是一个有向图中表示从一个节点能够到达的所有其他节点的矩阵。在 Python 中,可以使用 Floyd-Warshall 算法来求解可达矩阵。
以下是一个使用 Floyd-Warshall 算法求解可达矩阵的 Python 代码示例:
```python
INF = float('inf')
# 有向图邻接矩阵
graph = [
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 0]
]
# 初始化可达矩阵
reach_matrix = [[0 if i != j else 1 for j in range(len(graph))] for i in range(len(graph))]
# 使用 Floyd-Warshall 算法求解可达矩阵
for k in range(len(graph)):
for i in range(len(graph)):
for j in range(len(graph)):
if graph[i][j] == 1 or (graph[i][k] == 1 and graph[k][j] == 1):
reach_matrix[i][j] = 1
# 打印可达矩阵
for row in reach_matrix:
print(row)
```
运行以上代码,将会输出如下结果:
```
[1, 1, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 1, 0]
[0, 0, 1, 1, 0]
[0, 0, 0, 1, 1]
```
以上结果表示从每个节点出发能够到达的其他节点。例如,第一行表示从第一个节点出发可以到达所有其他节点。