路径压缩，此代码如何进行路径压缩？

-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

路径压缩，此代码如何进行路径压缩？

回答

相关问题