python - python中的图形连接

Question

我对图论不是很熟悉，但我会尽力解释我的问题。我有一个这样的字典:

{67: [68, 332],
 68: [67],
 265: [266],
 266: [265],
 332: [67, 333],
 333: [332, 334],
 334: [333, 335],
 335: [334, 336],
 336: [335]}

这个字典的键是节点，值是图的边。我们怎样才能找到这个图中的连接组？[有两组 - 265->266 和 67->...->366]

Answer 1

看起来您的图是无向的，这意味着对于任意两个节点 A 和 B，如果从 A 到 B 有一条边，则从 B 到 A 也有一条边。要找到图的连通分量，你可以简单地使用 depth-first search .从任何节点开始并沿着边缘移动，直到您无法到达更多节点而不击中重复项。这是第一个连接的组件。然后从您尚未触及的任何节点开始并重复。当您到达图中的所有节点时，您就完成了。