将图形转换为字典形式

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}})

Answer 2

下面是使用列表推导的简洁方法：

d = {k: dict((list(v[0] ^ {k})[0], v[1]) for v in G[1] if k in v[0]) for k in G[0]}
print(d)
#{'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}}

分解：

{k: ... for k in G[0]} 正在迭代 G 的第一个元素以获取输出字典的键。
{k: (... for v in G[1] if k in v[0]) ... } 是 G 中第二个元素的生成器表达式，如果键 k 包含在集合中，它将生成一个值。
v[0] ^ {k} 是集合与密钥的对称差异 - 这将从集合中删除密钥。
list(v[0] ^ {k})[0] 将集合转换为列表并获取第一个元素。这假设集合中始终只有 2 个元素，其中一个是键。
(list(v[0] ^ {k})[0], v[1]) 创建一个元组，其中第二个值是数字。
dict([(list(v[0] ^ {k})[0], v[1]) ... 在此元组列表上调用 dict 构造函数。

也许是一个更友好的版本，使用更合理的变量名而不是元组索引和set.pop()而不是列表索引：

d = {edge: dict(((pair ^ {edge}).pop(), value) for pair, value in G[1] if edge in pair) 
     for edge in G[0]}

将图形转换为字典形式

Converting a graph into dictionary form

python

dictionary

dijkstra

python-3.x