我正在使用 Python 的 networkx 包。
问问题
21290 次
5 回答
25
检查图中两个节点之间是否存在路径 -
>>> 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 文档
于 2013-10-27T16:36:54.437 回答
13
>>> 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"
...
>>>
于 2010-03-01T03:51:53.573 回答
10
使用不相交的集合数据结构:
为图中的每个顶点创建一个单例集,然后合并包含图中每条边的每个顶点对的集合。
最后,如果两个顶点在同一个集合中,则您知道它们之间存在一条路径。
请参阅关于不相交集数据结构的维基百科页面。
这比使用路径查找算法要有效得多。
于 2011-04-14T15:38:29.673 回答
7
利用
shortest_path(G, source, target)
或最短路径方法之一。但是,如果您只有两个特定节点来测试连接性,请不要使用返回所有节点之间路径的方法。
于 2010-03-01T03:52:41.310 回答
3
dijkstra_path(G, source, target)
返回加权图 G 中从源到目标的最短路径。
于 2010-03-01T03:43:59.490 回答