python - 将图形转换为字典形式

Question

我目前正在编写一个程序来模拟 Dijkstra 的算法，但是我在以下当前形式的图表中遇到了一些问题:

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 2), ({'d', 'g'}, 7), ({'d', 'h'}, 1) ,
      ({'e', 'i'}, 2), ({'e', 'j'}, 7), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

我想得到如下图形式的图表

{ 'a': {'b': 4, 'c': 6, 'd': 8},
    'b': {'a': 4, 'e': 1, 'f': 9}, etc

这可能吗？

Answer 1

您可以使用 collections.defaultdict为此。

代码:

from collections import defaultdict

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 2), ({'d', 'g'}, 7), ({'d', 'h'}, 1) ,
      ({'e', 'i'}, 2), ({'e', 'j'}, 7), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

result = defaultdict(dict)
for edge in G[1]:
    v1, v2 = edge[0]
    result[v1][v2] = edge[1]
    result[v2][v1] = edge[1]

print(result)

输出:

defaultdict(<class 'dict'>,
            {'a': {'b': 4, 'c': 6, 'd': 8},
             'b': {'a': 4, 'e': 1, 'f': 9},
             'c': {'a': 6, 'f': 2},
             'd': {'a': 8, 'g': 7, 'h': 1},
             'e': {'b': 1, 'i': 2, 'j': 7},
             'f': {'b': 9, 'c': 2},
             'g': {'d': 7, 'h': 2},
             'h': {'d': 1, 'g': 2},
             'i': {'e': 2, 'j': 4},
             'j': {'e': 7, 'i': 4}})