Python：如何在图中查找两个节点之间是否存在路径？

Question

我正在使用Python的networkx包。

- Bruce

Answer 1

检查图中是否存在两个节点间的路径 -

>>> import networkx as nx
>>> G=nx.Graph()
>>> G.add_edge(1,2)
>>> G.add_edge(2,3)
>>> nx.has_path(G,1,3)
True
>>> G.add_edge(4,5)
>>> nx.has_path(G,1,5)
False

获取更多信息，请参考has_path — NetworkX 1.7 文档

- Denny Abraham Cheriyan

Answer 2

>>> import networkx as nx
>>> G=nx.empty_graph()
>>> G.add_edge(1,2)
>>> G.add_edge(2,3)
>>> G.add_edge(4,5)
>>> nx.path.bidirectional_dijkstra(G,1,2)
(1, [1, 2])
>>> nx.path.bidirectional_dijkstra(G,1,3)
(2, [1, 2, 3])
>>> nx.path.bidirectional_dijkstra(G,1,4)
False
>>> nx.path.bidirectional_dijkstra(G,1,5)
False
>>> 

你也可以将结果用作布尔值

>>> if nx.path.bidirectional_dijkstra(G,1,2): print "path exists"
... 
path exists
>>> if nx.path.bidirectional_dijkstra(G,1,4): print "path exists"
... 
>>> 

- John La Rooy

Answer 3

使用不相交集数据结构：

为图中的每个顶点创建一个单例集合，然后对于图中的每条边，将包含每一对顶点的集合合并。

最后，如果两个顶点在同一个集合中，则知道它们之间存在一条路径。

请参见维基百科上的有关不相交集数据结构的页面。

这比使用路径查找算法要高效得多。

- Alex

---

嗯，我最近刚为自己实现了这个功能，而且它运行良好。 :-) - ericmjl

Answer 4

使用

shortest_path(G, source, target)

或者使用最短路径算法之一。但是，如果您只需要测试两个特定节点之间的连通性，请避免返回所有节点之间路径的方法。

- mjv

Answer 5

• dijkstra_path(G, source, target)

  在加权图G中，返回从源节点到目标节点的最短路径。

- miku

---

如果两个给定的节点之间不存在路径会怎么样？函数会返回什么？ - Bruce

我不想找到最短的路径，我只想知道是否存在两个给定节点之间的路径。 - Bruce