在Python中查找无向图组件的数据结构

Question

一个无向图可以用一对节点来表示：

边 = (A,B),(B,C),(D,E),(F,E),(G,E),(G,I),(H,G)

在Python中，想要找到一个特定子图的组成部分，给定一个起始边（比如说 (D,E)），最好的数据结构是什么呢？我在考虑使用深度优先搜索作为查找算法。

Answer 1

如果你只想要一个轻量级的数据结构，可以使用一个双向链表（实际上是无向的）配对字典。

节点结构：

{"name": "某个名字" , "connections": [连接的节点列表]}

你数据中的一些节点：

e = {"name": "E"}
d = {"name": "D"}
f = {"name": "F"}
g = {"name": "G"}

e["connections"] = [d,f,g]
#... etc with whatever code you want to build the graph itself

然后你可以使用任何你想要的算法。如果你想了解具体的算法，请调整一下你的问题。正如mvanveen提到的，如果可以的话，使用一个图形库。这方面已经有很多成熟的解决方案了。

Answer 2

你有没有看过 networkx 这个库？如果你不是从零开始，这个库提供了很棒的基本数据结构，可以用来处理各种形状和大小的图。

里面有一个 Graph.subgraph 方法，你可以在 这里 查看详细信息。

根据文档：

>>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_path([0,1,2,3])
>>> H = G.subgraph([0,1,2])
>>> H.edges()
[(0, 1), (1, 2)]