python - 如何从列表中创建邻接矩阵？

Question

我有一个这样的列表:

[['10', '20', 2], ['10', '21', 2], ['10', '1', 2], ['10', '0', 3], ['10', '3', 2],
 ['10', '2', 2], ['10', '5', 3], ['10', '4', 3], ['10', '7', 2], ['10', '6', 2],
 ['10', '9', 2], ['10', '8', 2], ['10', '11', 2], ['10', '10', 2], ['10', '13', 2],
 ['10', '12', 2], ['10', '15', 2], ['10', '14', 2], ['10', '17', 0], ['10', '16', 3],
 ['10', '19', 2], ['10', '18', 2], ['1', '20', 3], ['1', '21', 3], ['1', '1', 3],
 ['1', '0', 0], ['1', '3', 3], ['1', '2', 3], ['1', '5', 4], ['1', '4', 4],
 ['1', '7', 3], ['1', '6', 3], ['1', '9', 3], ['1', '8', 3], ['1', '11', 3],
 ['1', '10', 3], ['1', '13', 3], ['1', '12', 3], ['1', '15', 3]]

(比这大很多)第一项和第二项实际上是节点名称，第三项是它们之间的边权重(虽然我没有制作图表，它是一个列表)。

我想从这个列表中创建一个邻接矩阵。

Answer 1

是的，您可以使用 defaultdict 来做到这一点

In [1]: in_list =  [['10', '20', 2], ['10', '21', 2], ['10', '1', 2], ['10', '0', 3], ['10', '3', 2], ['10'
   ...: , '2', 2], ['10', '5', 3], ['10', '4', 3], ['10', '7', 2], ['10', '6', 2], ['10', '9', 2], ['10', '
   ...: 8', 2], ['10', '11', 2], ['10', '10', 2], ['10', '13', 2], ['10', '12', 2], ['10', '15', 2], ['10',
   ...:  '14', 2], ['10', '17', 0], ['10', '16', 3], ['10', '19', 2], ['10', '18', 2], ['1', '20', 3], ['1'
   ...: , '21', 3], ['1', '1', 3], ['1', '0', 0], ['1', '3', 3], ['1', '2', 3], ['1', '5', 4], ['1', '4', 4
   ...: ], ['1', '7', 3], ['1', '6', 3], ['1', '9', 3], ['1', '8', 3], ['1', '11', 3], ['1', '10', 3], ['1'
   ...: , '13', 3], ['1', '12', 3], ['1', '15', 3]]                                                        

In [2]: from collections import defaultdict

In [3]: tree = lambda: defaultdict(tree)

In [5]: adj_mat = tree()

In [6]: for edge in in_list:
   ...:     start, end, weight = edge
   ...:     adj_mat[start][end] = weight
   ...:                                 

In [7]: adj_mat
Out[7]:        
defaultdict(<function __main__.<lambda>>,
            {'1': defaultdict(<function __main__.<lambda>>,
                         {'0': 0,                          
                          '1': 3,                          
                          '10': 3,                         
                          '11': 3,                         
                          '12': 3,                         
                          '13': 3,                         
                          '15': 3,                         
                          '2': 3,                          
                          '20': 3,                         
                          '21': 3,                         
                          '3': 3,                          
                          '4': 4,                          
                          '5': 4,                          
                          '6': 3,
                          '7': 3,
                          '8': 3,
                          '9': 3}),
             '10': defaultdict(<function __main__.<lambda>>,
                         {'0': 3,
                          '1': 2,
                          '10': 2,
                          '11': 2,
                          '12': 2,
                          '13': 2,
                          '14': 2,
                          '15': 2,
                          '16': 3,
                          '17': 0,
                          '18': 2,
                          '19': 2,
                          '2': 2,
                          '20': 2,
                          '21': 2,
                          '3': 2,
                          '4': 3,
                          '5': 3,
                          '6': 2,
                          '7': 2,
                          '8': 2,
                          '9': 2})})

当我实现这个时，我注意到你所有的边缘都起源于 1 或 10。嗯，很奇怪。

解释

1. defaultdict 只是一个生动的 HashMap 的奇特名称(如果您有 perl 背景)
2. 矩阵中的条目是边权重
3. 如果你的边是双向的，你只需要在 for 循环中添加 adj_mat[end][start] = weight