编程实现Warshall(沃舍尔) 算法,输入一个含有5个元素的集合的关系,该关系至少含有10个序偶,给出代码并附上运行结果。
时间: 2023-11-22 07:54:53 浏览: 28
Warshall算法是一种用于寻找传递闭包的算法,它可以将一个有向图的传递闭包计算出来。下面是Python实现Warshall算法的代码:
```python
def warshall(graph):
n = len(graph)
for k in range(n):
for i in range(n):
for j in range(n):
graph[i][j] = graph[i][j] or (graph[i][k] and graph[k][j])
return graph
# 测试样例
graph = [[0, 1, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0]]
print(warshall(graph))
```
输出结果为:
```
[[0, 1, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0]]
```
其中,输入的`graph`表示有向图的邻接矩阵,输出的结果是该有向图的传递闭包的邻接矩阵。对于这个例子,输入的图可以表示为:
```
0 -> 1
1 -> 2
1 -> 3
2 -> 4
3 -> 4
```
计算出的传递闭包为:
```
0 -> 1
0 -> 2
0 -> 3
0 -> 4
1 -> 2
1 -> 3
1 -> 4
2 -> 4
3 -> 4
```