路徑壓縮，此代碼如何進行路徑壓縮？

-5

/* 
* To change this license header, choose License Headers in Project Properties. 
* To change this template file, choose Tools | Templates 
* and open the template in the editor. 
*/ 
package algorithm1; 

/** 
* 
* @author Navin 
*/ 

public class QuickUnionWeighted { 


private int [] id; 
private int [] size; 
int numberOfChild; 
int j=0; 

public QuickUnionWeighted(int N){ 

    id = new int[N]; 
    size = new int[N]; 

    for(int i=0;i<N;i++){ 

     id[i] = i; 
     size[i]=1; 
    } 


} 

public int root(int i){ 

    while (i != id[i]){ 
     id[i] = id[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); 

//   if(i == j) return; 

    if(size[i] < size[j]){ 

     id[i] = j; 
     size[j] += size[i]; 
    }else{ 
     id[j] = i; 
     size[i] +=size[j]; 
    } 


    for(int k=0;k<size.length;k++){ 
     System.out.print(size[k]+" "); 

    } 

} 


public static void main(String [] args){ 


    QuickUnionWeighted quw = new QuickUnionWeighted(10); 


    quw.union(3,0); 
    quw.union(4, 0); 
    quw.union(3, 5); 
    quw.union(3, 6); 
    quw.union(3,9); 



} 



}

因爲當我檢查代碼時，id[i] = id[id[i]]指向節點的父節點，並且檢查的節點沒有移動到其祖父母，並且樹未平坦化。路徑壓縮，此代碼如何進行路徑壓縮？

親切指導。

來源

2015-11-30 naveenath

我下來（和特寫）投票這個問題，因爲目前尚不清楚你想到這個代碼做什麼。如果你給出更多的解釋，你可能會得到更多的幫助，你想要用這個代碼做什麼，它實際上做了什麼以及爲什麼你不理解這種行爲。 –

id[i] = id[id[i]];

這條線是路徑壓縮。 id[i]是節點i的父級。因此，該行將節點i重新鏈接到其父母。因此，它跳過了父項。然後，同樣的事情發生在祖父母等等。這使樹變平了。

下面是這一步的可視化：

1     1 
^     /\ 
|  root(3) / \ 
2 --------> 2  3 
^ 
| 
3

來源

2015-11-30 18:31:58

路徑壓縮，此代碼如何進行路徑壓縮？

回答

相關問題