遍歷連接的組件

我想遍歷包含頂點的無向圖的每個連接組件。即我想調用每個向量V 一些函數f（V _我）... V _ķ其中V _我是含有連接到每個節點中的第i個連接分量的數據的矢量圖形。遍歷連接的組件

這樣做最快的算法是什麼？

我的第一個想法是：

存放在一個堆所有未訪問頂點，然後反覆地頂點離堆，使用DFS找到它的連接分量V _我，調用F（V _我）並從堆中刪除組件中的所有頂點。
查找union-find不相交集合的變體，它不僅支持高效設置聯合，而且還可以高效地遍歷集合並查找其成員。（這可能嗎？）

來源

2016-10-04 Angela Richardson

當然DFS是一個辦法做到這一點，但它可能取決於如果你想優化這個用於一次性計算，或計算，將經常發生。有了更多的訣竅，你不需要每次重新發現連接的組件。 – AndyG

爲什麼你需要一堆？使用簡單的哈希集，DFS/BFS都可以工作，並且是您可以做到的最優化。 –

我們可以假設您將圖存儲爲鄰接列表嗎？我們可以假設頂點從0到N-1編號，其中N是頂點的總數？ – pkacprzak

運行經典connected components algorithm。通常，這操縱一個disjoint-sets data structure。
創建一個哈希表映射節點到鏈接的節點列表。
遍歷每個節點

a。在不相交集數據結構中找到代表節點

b。如有必要，爲散列表中的代表性節點創建鏈接列表

c。節點添加到與代表性節點

相關的鏈表這有效地花費線性時間（即Θ（| E | + | V |），預期（根據廣泛接受的理解是不相交的集合是有效的線性時間）

現在你有一個哈希表，其條目數是連接組件的數量，每個值都是連接組件中所有節點的鏈表，現在你可以線性地迭代任何你想要

來源

2016-10-04 13:26:30

是的DFS是一個很好的選擇爲此。但請記住，如果運行遞歸DFS，給定範圍10^7個節點可能會遇到內存問題。因爲在麥汁情況下，所有節點將使鏈，您將需要巨大的規模在堆棧，造成計算器（：d）

嘗試這樣做：用階爲O

DFS使用堆棧（非遞歸DFS）（ V + E），或
使用簡單的BFS（最好的選擇考慮到簡單，在這裏節點的數量）順序（V + E）

BFS通常用於最短路徑問題，但它可以在許多使用其他應用程序，如這一個。這將從隊列數據結構的堆中佔用空間，通常的遞歸DFS佔用堆棧中的空間。

來源

2016-10-04 13:55:36

如果您將圖存儲爲鄰接列表，並且頂點由從1到n-1的整數表示，那麼不需要聯合查找或散列表。

我們假設g[v]是與v相鄰的頂點列表（向量）。此外，讓cc爲列表（矢量向量）的列表，其中cc[i]表示連接組件中的頂點。爲了實施目的，當且僅當我們檢查DFS例程中的v時，我們要使用visited[v] = true。然後僞代碼看起來像這樣：

dfs(v, current_cc): 
    visited[v] = true 
    current_cc.append(v) 
    for u in g[v]: 
     if not visited[u]: 
     dfs(u, current_cc) 

for v = 0 to n-1: 
    visited[i] = false 

for v = 0 to n-1: 
    if not visited[v]: 
     current_cc = [] 
     dfs(v, current_cc) 
     cc.append(current_cc) 

//From now, cc[i] is a list of vertices in the i-th connected component, 
//so we can easily iterate and call whatever we want on them.

來源

2016-10-04 14:02:21 pkacprzak

遍歷連接的組件

回答

相關問題