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__以提高访问时间和存储效率，因为矩阵是对称的。

Answer 2

我喜欢 python 中像这样的二维结构的元组键。

{(1, 1): 0, (3, 2): 9... }

我认为它在概念上最清晰，因为它删除了上述解决方案中的中间数据结构。尽管如此，如果您打算以行或列方式访问结构，则该中间数据结构（内部列表或行/列）可能很有用。

 for x, row in enumerated(matrix, 1):
       # process whole row 
       for y in enumerate(row, 1):
             # process cell...

但是，如果您的游戏是按单元格进行数据访问，那么为了表达的简单性，很难击败以下内容：

for (x, y), value in matrix.iteritems():
      # act on cell

如果您愿意，请对其进行排序。

 # (1, 1), (1, 2)...
 for (x, y), value in sorted(matrix.iteritems()):
       # act on cell