将邻接矩阵转换为字典的有效方法是什么？

Question

我想知道将邻接矩阵转换为表示一个节点与另一个节点之间的连接的字典的有效方法是什么？

示例矩阵：

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

Answer 1

这是一个更 Pythonic 的解决方案，可能会更快一些。

{i: [j for j, adjacent in enumerate(row) if adjacent] for i, row in enumerate(matrix)}

我怀疑你在原始 Python 中会变得更快。我会考虑是否有任何解决方案可以利用快速库，例如 numpy.

更新：我使用以下方法为两个解决方案计时。

import numpy as np

# Make a big example
num_nodes = 1000
matrix = np.random.randint(0, 2, [num_nodes, num_nodes])

# Convert to raw Python
matrix = [[element for element in row] for row in matrix]

你的解决方案用了 0.62 秒，我的用了 0.12 秒。所以实际上有大约 5 倍的加速。

Answer 2

使用 NumPy 在每行中定位非零元素可以获得更好的性能：

import numpy as np
{i: np.nonzero(row)[0].tolist() for i,row in enumerate(matrix)}

随机 1000x1000 矩阵的时间：

原码：310ms
@Denxiloe 的代码：91ms
这段代码：20ms

将邻接矩阵转换为字典的有效方法是什么？

What is an efficient way to convert an adjacency matrix to a dictionary?

python

dictionary

for-loop

adjacency-matrix

adjacency-list