Boruvka算法的複雜度如何可能爲O（E * logV）？

Question

1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T 
2 While the vertices of G connected by T are disjoint: 
3 Begin with an empty set of edges E 
4 For each component: 
5  Begin with an empty set of edges S 
6  For each vertex in the component: 
7  Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S 
8  Add the cheapest edge in S to E 
9 Add the resulting set of edges E to T. 
10 The resulting set of edges T is the minimum spanning tree of G. 

來自維基百科。自從你加入集合後，我明白外層循環是logV。但是接下來是內部循環。

如果您使用等價關係跟蹤集合，這意味着您只獲取表示集合的元素，因此您無法確定兩個集合之間權重最小的邊緣，因爲您沒有擁有所有元素。如果修改結構以保存對孩子的引用，則仍然需要獲取每個孩子的所有孩子。這意味着，更壞的情況下，每個集合的O（V/2）= O（V）。

之後，您仍然需要找到連接兩個組件的最小邊，這意味着要遍歷連接這兩個組件的所有邊。因此，您需要遍歷每個節點，並查看其邊緣是否連接到另一個組件中的某個元素，如果它的確如此，那麼它是否比您當前擁有的最小邊緣更小。

意義，一個外部循環遍歷節點和一個內部循環遍歷該節點的邊緣 - O（V E）。由於它在O（logV）循環內部，因此可以得到O（logV V * E）。

現在，您似乎只需遍歷所有邊，但您將如何選擇2個組件之間的最小邊？我可以判斷給定的邊是否連接了不同組件中的節點，但我無法判斷哪個連接節點具有最小權重。如果我得到最小重量的那個，它可能不會連接它們。

Answer 1

如果允許散列表，那麼我會看到它是如何成爲O（Elog N）算法的。 每個組件都存儲爲不同的哈希集。最初，每個集合都包含一個節點。爲所有組件尋找最小「橋」的步驟需要O（E）個時間，因爲我們最多檢查兩個邊，並假設在散列集中進行恆定時間查找。然後我們繼續合併集合，這需要O（N）時間。由於圖連通，E> = N-1，因此每次迭代的總成本爲O（E）。

- 編輯 -

繼throwawayacct的評論，也沒有必要對哈希結構在所有。在每次迭代中，我們都有一個由前一次迭代產生的森林圖，所以我們可以在O（E）時間內重新計算它的連通分量。這可以通過例如來自所有節點的簡單DFS遍歷來完成，其爲每個組件設置獨特的「顏色」。然後，當掃描邊緣以找到橋時，我們只考慮連接不同顏色節點的邊。