建立「連接矩陣」的成本

我確信有大量關於如何完成我所追求的信息，但這是一個不知道技術術語的問題。基本上我想創建的是一個有向圖的鄰接矩陣，而不是簡單地存儲每個頂點對是否具有鄰接關係，對於矩陣中的每個頂點對，如果存在任何路徑連接這兩個（以及那些路徑是什麼）。建立「連接矩陣」的成本

這會給我的查找帶來恆定的時間複雜度，但是我不明白這個矩陣的建築的預期最佳時間複雜度。

另外，是否有這樣的矩陣的正式名稱？

在我腦子裏玩這個，看起來像是一個動態的編程問題。如果我想知道A是否連接到Z，我應該能夠詢問A的每個鄰居B，C和D是否它們（以某種方式）連接到Z，如果是，那麼我知道A是。如果B沒有存儲這個答案，那麼他會問他同樣的問題他的直接的鄰居，等等。我會一路記錄結果，因此後續查找將保持不變。

我還沒有花時間去實現這個，因爲它感覺像Θ（n^n）來構建一個完整的矩陣，所以我的問題是我是否正在以正確的方式進行，如果的確，建立這樣一個矩陣的成本更低？

來源

2017-07-29 ricklane

計算它是definetly比'O（N 1，N）'便宜。您可以從每個節點執行BFS/DFS，並獲得'O（| E | * | V |）'解決方案。 – amit

謝謝@amit。我打算說n^2，但這仍然是不正確的。（我在考慮n是| V |）。所以我會O（E * V）一樣好。 – ricklane

準確地說，我認爲它是O（n *（n + 1）/ 2），考慮一條直線的簡單連通圖，其中每個頂點至多有一個鄰居。 – ricklane

圖的傳遞閉包（https://en.wikipedia.org/wiki/Transitive_closure#In_graph_theory）確實可以通過Floyd Warshall算法的變體動態編程來計算：https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm。

使用| V |雖然DFS（或BFS）更高效。

來源

2017-07-30 21:44:46

DFS/BFS更高效，但在我的情況下，我必須進行數十萬次搜索才能查看V1是否連接到V2，因此使用傳遞閉包將允許這些檢查爲O（1）。 – ricklane

您可以使用| V |來計算傳遞閉包的矩陣。 DFS，並在O（1）之後進行查詢。這是O（（| E | + | V |）| V |）而不是O（| V |^3）與Floyd Warshall（如果| E | = o（| V |^2）相同的目標。 –

使用networkx connected components

G = nx.path_graph(4) 
G.add_path([10, 11, 12]) 
d = {} 
for group in idx, group in enumerate(nx.connected_components(G)): 
    for node in group: 
     d[node] = idx 

def connected(node1, node2): 
    return d[node1]==d[node2]

代應該O(N)查找應O(1)

來源

2017-08-04 04:10:29

建立「連接矩陣」的成本

回答

相關問題