我想知道将邻接矩阵转换为表示一个节点与另一个节点之间的连接的字典的有效方法是什么?
示例矩阵:
matrix = [
[0,1,0,0,0,0],
[0,0,0,0,0,0],
[0,1,0,1,0,0],
[0,0,0,0,0,0],
[0,0,0,1,0,1],
[1,0,0,0,0,0]
]
示例输出:
{0: [1], 1: [], 2: [1, 3], 3: [], 4: [3, 5], 5: [0]}
我下面的代码实际上生成了正确的输出;但是,我认为这是非常低效的,因为我使用了两个 for 循环。有没有什么方法可以在不使用任何库的情况下优化我的代码?请告诉我,谢谢!
def convertAdjMatrixtoDict(m):
graph = {}
for idx, row in enumerate(m):
res = []
for r in range(len(row)):
if row[r] != 0:
res.append(r)
graph[idx] = res
return graph
最佳答案
使用 NumPy
在每一行中定位非零元素可以获得更好的性能:
import numpy as np
{i: np.nonzero(row)[0].tolist() for i,row in enumerate(matrix)}
随机 1000x1000 矩阵的时间:
- 原码:310ms
- @Denxiloe 的代码:91 毫秒
- 这段代码:20ms
关于python - 将邻接矩阵转换为字典的有效方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52322847/