Python：如何查找图中两个节点之间是否存在路径？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2353768/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python: How to find if a path exists between 2 nodes in a graph?
提问by Bruce
I am using networkx package of Python.
我正在使用 Python 的 networkx 包。
采纳答案by John La Rooy
>>> 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
>>>
You can also use the result as a boolean value
您还可以将结果用作布尔值
>>> if nx.path.bidirectional_dijkstra(G,1,2): print "path exists"
...
path exists
>>> if nx.path.bidirectional_dijkstra(G,1,4): print "path exists"
...
>>>
回答by Denny Abraham Cheriyan
To check whether there is a path between two nodes in a graph -
要检查图中两个节点之间是否存在路径 -
>>> 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
For more information, please refer has_path — NetworkX 1.7 documentation
更多信息请参考has_path — NetworkX 1.7 文档
回答by Alex
Using a disjoint set data structure:
使用不相交的集合数据结构：
Create a singleton set for every vertex in the graph, then union the sets containing each of the pair of vertices for every edge in the graph.
为图中的每个顶点创建一个单例集，然后合并包含图中每个边的每个顶点对的集合。
Finally, you know a path exists between two vertices if they are in the same set.
最后，如果两个顶点在同一个集合中，您就知道它们之间存在一条路径。
See the wikipediapage on the disjoint set data structure.
请参阅有关不相交集数据结构的维基百科页面。
This is much more efficient than using a path finding algorithm.
这比使用路径查找算法要高效得多。
回答by mjv
Use
利用
shortest_path(G, source, target)
or one of the Shortest Path methods. Stay clear of the methods which return paths between all nodes however if you merely have two specific nodes to test for connectivity.
或最短路径方法之一。但是，如果您只有两个特定节点来测试连接性，请不要使用返回所有节点之间路径的方法。
回答by miku
dijkstra_path(G, source, target)Returns the shortest path from source to target in a weighted graph G.
dijkstra_path(G, source, target)返回加权图 G 中从源到目标的最短路径。
