如何用python将邻接矩阵转换为邻接表？

Question

我有一个邻接矩阵，例如：

[[  0.,  15.,   0.,   7.,  10.,   0.],
    [ 15.,   0.,   9.,  11.,   0.,   9.],
    [  0.,   9.,   0.,   0.,  12.,   7.],
    [  7.,  11.,   0.,   0.,   8.,  14.],
    [ 10.,   0.,  12.,   8.,   0.,   8.],
    [  0.,   9.,   7.,  14.,   8.,   0.]]

我怎样才能将它转换为像下面这样的邻接列表？

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

保留集合中已添加边的列表edges。这些边存储在 a 中frozenset，因此已添加的边对不会被复制。

然后通过枚举起始索引为 1 的外部列表以及起始索引为 1 的内部列表来构建图表。零值条目将根据if值的条件被消除：

from collections import defaultdict
from pprint import pprint

l =[[  0.,  15.,   0.,   7.,  10.,   0.],
    [ 15.,   0.,   9.,  11.,   0.,   9.],
    [  0.,   9.,   0.,   0.,  12.,   7.],
    [  7.,  11.,   0.,   0.,   8.,  14.],
    [ 10.,   0.,  12.,   8.,   0.,   8.],
    [  0.,   9.,   7.,  14.,   8.,   0.]]    

graph = defaultdict(list)
edges = set()

for i, v in enumerate(l, 1):
    for j, u in enumerate(v, 1):
        if u != 0 and frozenset([i, j]) not in edges:
            edges.add(frozenset([i, j]))
            graph[i].append({j: u})

pprint(graph)
# {1: [{2: 15.0}, {4: 7.0}, {5: 10.0}],
#  2: [{3: 9.0}, {4: 11.0}, {6: 9.0}],
#  3: [{5: 12.0}, {6: 7.0}],
#  4: [{5: 8.0}, {6: 14.0}],
#  5: [{6: 8.0}]}

使用defaultdict以 a list作为默认值的 a 将有助于动态构建列表值字典。