Python：如何查找圖中2個節點之間是否存在路徑？

Question

我正在使用Python的networkx包。

Answer 1

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

Answer 2

• dijkstra_path(G, source, target)

  從源返回的最短路徑中的加權圖G來定位

Answer 3

使用

shortest_path(G, source, target) 

或其中一種最短路徑方法。如果只有兩個特定的節點來測試連通性，請保持清除所有節點之間返回路徑的方法。

Answer 4

使用不相交的集合的數據結構：

創建單爲圖中的每個頂點設置，那麼聯合含有一對頂點的對圖中的每一個邊緣的集。

最後，你知道兩個頂點之間存在一條路徑，如果它們在同一個集合中。

請參閱不相交集數據結構中的wikipedia頁面。

這比使用路徑尋找算法更有效率。

Answer 5

要檢查是否有一個圖中，兩個節點之間的路徑 -

>>> 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 documentation