Quick Union Java實現

我一直在研究快速聯合算法。下面的代碼是實現的例子。有人可以向我解釋根方法裏面發生了什麼嗎？Quick Union Java實現

public class quickUnion { 
private int[] id; 

public void QuickUnionUF(int N){ 
    id = new int [N]; 
    for(int i = 0; i < N; i++){ 
     id[i] = i; 
    } 
} 

private int root(int i){ 
    while (i != id[i]){ 
     i = id[i]; 
    } 
    return i; 
} 
public boolean connected(int p, int q){ 
    return root(p) == root(q); 
} 
public void union(int p, int q){ 
    int i = root(p); 
    int j = root(q); 
    id[i] = j; 
} 
}

來源

2017-05-03 Ifham

它繼續向上直到它找到根：這就是當id [i] ==我，其中id [我]是我的父母。請參閱幻燈片18在https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf –

[你的步調試器告訴你什麼？]（http://stackoverflow.com/questions/25385173/what-是一個調試器和如何可以幫助我診斷問題） –

我正在使用Eclipse IDE，我還沒有添加主要方法，我只是通過代碼。無論如何，答案解決了我的問題。 – Ifham

聯合查找的核心原則是每個元素都屬於一個不相交的元素集。這意味着，如果繪製一個森林（樹木），森林將包含所有的元素，並且沒有元素將在兩棵不同的樹中。

在構建這些樹時，可以想象任何節點都有父節點或是根節點。在聯合查找（以及大多數聯合查找實現）的此實現中，每個元素的父元素都存儲在該元素索引處的數組中。因此，與id [i]等價的元素是i的父元素。

你可能會問：如果我沒有父母（又名是根）怎麼辦？在這種情況下，約定是將我設置爲自己（我是它自己的父母）。因此，id [i] ==我只是檢查我們是否已經到達樹的根。

把這一切放在一起，根函數從起始節點遍歷樹（父代父），直到到達根。然後它返回根。

撇開：爲了讓這個算法更快地到達根目錄，一般的實現會使樹變平：需要通過根到達的父輩越少，根函數越快將返回。因此，在許多實現中，你會看到一個額外的步驟，將元素的父元素設置爲其原始祖父母（id [i] = id [id [i]]）。

來源

2017-05-03 17:11:17

算法的要點在於：始終保持一個頂點的根等於自身。

初始化：初始ID [i] = i。每個頂點本身就是一個根。
合併根：
- 如果我們合併根5和根6.假設我們希望根部6合併成根5.所以ID [6] = 5 ID [5] = 5 - > 5是根。
- 如果我們繼續合併4到6. id [4] = 4 - > base root。 id [6] = 5。 - >不是基礎根。我們繼續找到：id [5] = 5 - > base root。所以我們分配ID [4] = 6

在所有情況下，我們始終保持慣例：如果x爲根部，id[x] == x即算法的主要點。

來源

2017-05-03 17:19:46 hqt

Quick Union Java實現

回答

相關問題