如何在python中从输入文本文件实现图形？

Question

我有一个格式为的输入文件：

Stuttgart Nuremberg 207
Nuremberg Munich 171
Manchester Birmingham 84
Birmingham Bristol 85
Birmingham London 117
END OF INPUT

我想应用暴力算法来寻找两个城市之间的最短路径（距离），我需要将文本转换为图形。同样，图形需要动态生成，应该适用于这个或任何其他具有相同格式的输入文件。在

编辑：：您的回答有帮助，但它正在计算“输入结束”一行，因此我将代码修改为：

我试着像这样添加while循环：

^{pr2}$

图形

但它只适用于前两行。怎么了？在

Answer 1

有许多方法可以表示一个图，但最简单的方法之一是将节点字典转换为边列表，例如：

{
  'Stuttgart': [('Nuremberg', 207)],
  'Nuremberg': [('Munich', 171)],
  'Manchester': [('Birmingham', 84)],
  'Birmingham': [('Bristol', 85), ('London', 117)]
}

如果这是一个无向图，则需要添加边的倒数，例如：

^{pr2}$

对于大多数图算法来说，这应该是一个非常容易使用的结构。 对于您的问题，您将需要决定是否可以回溯（多次访问一个节点）以及您的图是否完全连接（您的示例数据没有），以决定适当的算法。在

您可以从您的文件（strawman）构建图形：

graph = {}   # or use defaultdict(list)
with open('<filename>', 'r') as f:
    for l in f:
         n1, n2, d = l.split()
         graph.setdefault(n1, []).append((n2, d))
         graph.setdefault(n2, []).append((n1, d))  # Undirected graph

有许多实现图算法的库，请查看networkx:https://networkx.github.io/看看这是否符合您的需要。在