使用快速联合算法对路径进行压缩，java

给定下面的代码块，取自quickunion算法，我需要向方法find（）添加一个循环，该方法将从站点p到站点p的路径中的每个站点链接起来根。我在这个网站上看到了一些其他类似的问题和答案，但答案似乎彼此不同，我不相信他们以我尝试这样做的方式执行压缩。任何帮助都将非常感谢！使用快速联合算法对路径进行压缩，java

public int find(int p) 
{ //Find component name.  
while (p != id[p]) p = id[p]; 
return p; 
} 

public void union(int p, int q) 
{ //Give p and q the same root. 
int i = find(p); 
int j = find(q); 
if (i==j) return; 

id[i] = j; 

count--; 
}

来源

2014-02-12 user3245237

我正确的假设你发现了一堆不同的方式来执行路径压缩？那是问题吗？当然不只有一种方法可以做到这一点 - 这往往不是这种情况。 “（你想要[（或想要）]这样做的方式是什么”？ – Dukeling

你看到的其他例子是什么？它们有什么不同？ – rockinfresh

是的确有很多方法。我看到的其他例子会通过将网站链接到祖父母来执行压缩。 – user3245237

你可以用双循环来做到这一点，首先找到根，然后设置所有指向它。

public int find(int p) 
{ int curr = p; 
    while (curr != id[curr]) curr = id[curr]; //find root 
    //at this point, curr is the root 
    while (p != id[p]) { 
     int next = id[p]; 
     id[p] = curr; //remember, curr is the root 
     p = next; 
    } 
}

来源

2014-02-12 14:05:06 amit

使用快速联合算法对路径进行压缩，java

回答

相关问题