python - Python 中的邻接矩阵

Question

关于如何在 Python 中创建考虑权重的邻接矩阵，我找不到任何明确的解释。我认为创建起来应该相对简单。

我有以下矩阵...

   1   2   3   4   5   6
1  0   15  0   7   10  0
2  15  0   9   11  0   9
3  0   9   0   0   12  7
4  7   11  0   0   8   14
5  10  0   12  8   0   8
6  0   9   7   14  8   0

数字1到6是顶点，里面的数字是每个相邻顶点之间的权重。例如，边 1-2 的权重为 15。

我如何在 python 中实现它？我只需要一个简单的示例，不一定使用我提供的示例。

我知道如何创建邻接表...

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}],
    '2': [{'3':'9'}, {'4':'11'}, {'6':'9'}],
    '3': [{'5':'12'}, {'6':'7'}],
    '4': [{'5':'8'}, {'6':'14'}],
    '5': [{'6':'8'}]}

但我需要一个邻接矩阵。

Answer 1

我认为存储邻接矩阵最常见和最简单的概念是使用二维数组，在python中对应于嵌套列表

mat = [[0, 15, 0, 7, 10, 0], [15, 0, ...], [...], [...]]
m[0][1]  # = 15 (weight of 1-2)

如果值是只读的，您可以使用嵌套元组代替:)

当然，您可以随心所欲地使用字典或编写类并重新定义 __getattr__ 以提高访问时间和存储效率，因为矩阵是对称的。