写在前面
这里给出加权图的邻接矩阵和邻接表的转换, 格式是按照networkx的格式来的.
注意这里的矩阵遵循: 自己跟自己距离为0, 不邻接的两个节点距离为inf, 但是在networkx中, 邻接矩阵中的inf都使用0来替代.
代码
"""
adjacent matrix <=> adjacent list
with weights
"""
from math import inf
def matrix2list(matrix):
result = []
N = len(matrix)
for i in range(N):
tmp1 = []
for j in range(N):
if matrix[i][j] and matrix[i][j] != inf:
tmp1.append(((i, j), matrix[i][j]))
result.extend(tmp1)
return result
def list2matrix(table):
N = 0
# 找到结点数目
for i in range(len(table)):
N = max(*table[i][0], N)
# 这里不能直接使用列表乘法
ret = [[inf] * (N + 1) for _ in range(N + 1)]
# 对角线置零
for i in range(N + 1):
ret[i][i] = 0
# 开始赋值
for (i, j), w in table:
ret[i][j] = w
return ret
matrix = [
[0, 2, inf, inf, inf],
[2, 0, inf, 3, 2],
[inf, inf, 0, inf, 1],
[inf, 3, inf, 0, 4],
[inf, 2, 1, 4, 0]
]
tb = matrix2list(matrix)
print(tb)
for (i, j), k in tb:
print((i, j), k, sep="\t\t")
tb1 = [((0, 1), 2), ((1, 0), 2), ((1, 3), 3), ((1, 4), 2),
((2, 4), 1), ((3, 1), 3), ((3, 4), 4), ((4, 1), 2),
((4, 2), 1), ((4, 3), 4)]
mat = list2matrix(tb1)
print(mat)
# [[0, 2, inf, inf, inf],
# [2, 0, inf, 3, 2],
# [inf, inf, 0, inf, 1],
# [inf, 3, inf, 0, 4],
# [inf, 2, 1, 4, 0]]