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

Question

我正在使用Python的networkx库。

Answer 1

使用不相交集合的数据结构：

为图中的每个顶点创建一个单独的集合，然后对于图中每条边的每对顶点，将它们各自的集合合并在一起。

最后，如果两个顶点在同一个集合里，就说明它们之间存在路径。

可以查看维基百科上关于不相交集合数据结构的页面。

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

Answer 2

要检查图中两个节点之间是否有路径，可以使用以下方法 -

>>> 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 文档

Answer 3

>>> 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"
... 
>>> 

你也可以把结果当作布尔值来使用