Python -如何将一个列表转换为邻接列表的图结构

Question

我的问题是我不能将通过列表构造的图转换为作为字典构造的图，而字典必须充当邻接表。

我已经构造了一个随机生成的图，随机添加到每条边:开始节点(string)，结束节点(string)，权重(int)。但是现在我需要把它转换成这样一个表示邻接表的图(一个字典):

example_graph = {
'A': {'B': 2, 'C': 3},
'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
'C': {'A': 3, 'B': 1, 'F': 5},
'D': {'B': 1, 'E': 1},
'E': {'B': 4, 'D': 1, 'F': 1},
'F': {'C': 5, 'E': 1, 'G': 1},
'G': {'F': 1},
}

这些图形必须是相同的，这就是为什么我需要转换第一个。接下来我要做的就是将这三个初始值(起始节点，结束节点，权重)放入一个名为graphConvert的列表中，如下所示:

while i < graph.numberOfNodes():
graphConvert.insert(i, list(zip(graph.edges[i].node1.printSingleNode(), graph.edges[i].node2.printSingleNode(), [graph.edges[i].weight])))
deleteIntegers.append(graph.edges[i].weight)
i += 1
deleteIntegers = list(set(deleteIntegers))

这是一个例子的结果:[[(' C ', ' B ', 4)], [(' A ', ' D ', 2)]、[(' D ', ' C ', 3)], [(' A ', ' C ', 4)]]

然后我添加了以下代码将列表转换为字典:

adj_list = {}
for edge_list in graphConvert:
for edge in edge_list:
for vertex in edge:
adj_list.setdefault(vertex, set()).update((set(edge) - {vertex}))
for i in range(deleteIntegers.__len__()):
adj_list.__delitem__(deleteIntegers[i])

的结果:{"C":{" B ", 3, 4, ' D ', ' '}, B: {' C ' 4},":{' C ' 2 ' D ', 4},"D":{3 ' C ' 2 ' '}}

我希望获得这样的:{"C":{B: 4, ' D ': 3, ' ': 4}, B:{"C":4},":{' C ' ' D ': 2: 4},等等。

但是正如你所看到的结果是不正确的，我不知道如何解决这个问题。例如，我不明白如何在到达节点的权重之前停止For循环并无意义地打印它，但是之后我必须插入它以正确显示开始和结束节点之间的距离。但这只是我不理解的事情之一，也是这个项目的问题所在。我已经绞尽脑汁想了一段时间了，但我还是没有掌握它的窍门，也许我需要休息一下!我使用python的时间不长，所以我还有很多东西要学。提前感谢任何回答我的人!

Answer 1

您可以使用defaultdict:

from collections import defaultdict
graph_to_convert = [[('C', 'B', 4)], [('A', 'D', 2)], [('D', 'C', 3)], [('A', 'C', 4)]]
g = defaultdict(dict)
for edge in graph_to_convert:
a,b,w = edge[0]
g[a][b] = w
print(g)
#defaultdict(<class 'dict'>, {'C': {'B': 4}, 'A': {'D': 2, 'C': 4}, 'D': {'C': 3}})

如果您不满意最终结果为defaultdict，您可以添加g = dict(g)行，将结果强制转换为直接的dict。