加权快速联盟与路径的COM pression算法 [英] Weighted Quick-Union with Path Compression algorithm
问题描述
有一个加权快速联盟与路径的COM pression算法。
在code：
公共类WeightedQU
{
私人INT [] ID;
私人INT [] IZ;
公共WeightedQU（INT N）
{
ID =新INT [N];
IZ =新INT [N];
的for（int i = 0; I＆LT; id.length;我++）
{
IZ [我] =我;
ID [我] =我;
}
}
公众诠释根（int i）以
{
而（我！= ID [I]）
{
ID [i] = ID [ID [I]]; //这一行再presents路径COM pression
I = ID [I]
}
返回我;
}
连接公共布尔（INT磷，INT Q）
{
返回根（P）==根（Q）;
}
公共无效联盟（INT磷，INT Q）//这里IZ []是用来加权
{
INT I =根（P）;
INT J =根（Q）;
如果（IZ [1] - ; IZ [J]。）
{
ID [i] = j的;
IZ [J] + = IZ [I]
}
其他
{
ID [J] =我;
IZ [I] + = IZ [J]。
}
}
}
问题：
-
如何路径COM pression工作？
ID [I] = ID [ID [I]]意味着我们达到我们的节点只有第二祖先，没有根。 -
IZ []包含0整数N-1。如何IZ []帮助我们了解集合中元素的个数？
有人可以澄清这对我？
首先理解 ID 是森林。 ID [I] 是的母公司我。如果 ID [I] ==我这意味着我是一个根。
对于一些根我（其中 ID [I] ==我），那么 IZ [I] 的元素在乔木数量一个植根于我。
公众诠释根（int i）以
{
而（我！= ID [I]）
{
ID [i] = ID [ID [I]]; //这一行再presents路径COM pression
I = ID [I]
}
返回我;
}
如何路径COM pression工作？
ID [I] = ID [ID [I]]意味着我们达到我们的节点只有第二祖先，没有根。
由于我们正在提升树上找到我们移动节点离开父母到祖父母的根源。这部分地变平了树。请注意，此操作不会更改该树的节点是一个成员，这是我们所感兴趣的是，这是路径COM pression技术。
（你也注意到循环吗？同时（我== ID [I]）终止一旦我是根节点）
IZ []包含0整数N-1。如何IZ []帮助我们了解集合中元素的个数？
有一个在code转录错误：
的for（int i = 0; I＆LT; id.length;我++）
{
IZ [我] =我; // 错误
ID [我] =我;
}
这是正确的版本：
的for（int i = 0; I＆LT; id.length;我++）
{
IZ [I] = 1; // 对
ID [我] =我;
}
IZ [I] 是一个植根于一棵树我（或<$ C元素的数量$ C>我不是根则 IZ [I] 是不确定的）。因此，它应该被初始化为 1 ，不是我。开始时，每个元素大小的单独的单身树 1 。
There is a "Weighted Quick-Union with Path Compression" algorithm.
The code:
public class WeightedQU
{
private int[] id;
private int[] iz;
public WeightedQU(int N)
{
id = new int[N];
iz = new int[N];
for(int i = 0; i < id.length; i++)
{
iz[i] = i;
id[i] = i;
}
}
public int root(int i)
{
while(i != id[i])
{
id[i] = id[id[i]]; // this line represents "path compression"
i = id[i];
}
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q) // here iz[] is used to "weighting"
{
int i = root(p);
int j = root(q);
if(iz[i] < iz[j])
{
id[i] = j;
iz[j] += iz[i];
}
else
{
id[j] = i;
iz[i] += iz[j];
}
}
}
Questions:
How does the path compression work?
id[i] = id[id[i]]means that we reach only the second ancester of our node, not the root.iz[]contains integers from0toN-1. How doesiz[]help us know the number of elements in the set?
Can someone clarify this for me?
First understand that id is a forest. id[i] is the parent of i. If id[i] == i it means that i is a root.
For some root i (where id[i] == i) then iz[i] is the number of elements in the tree rooted at i.
public int root(int i)
{
while(i != id[i])
{
id[i] = id[id[i]]; // this line represents "path compression"
i = id[i];
}
return i;
}
How does the path compression work?
id[i] = id[id[i]]means that we reach only the second ancester of our node, not the root.
As we are ascending the tree to find the root we move nodes from their parents to their grandparents. This partially flattens the tree. Notice that this operation doesn't change which tree the node is a member of, this is all we are interested in. This is the path compression technique.
(You did notice the loop right? while(i == id[i]) terminates once i is a root node)
iz[]contains integers from0toN-1. How doesiz[]help us know the number of elements in the set?
There is a transcription error in the code:
for(int i = 0; i < id.length; i++)
{
iz[i] = i; // WRONG
id[i] = i;
}
This is the correct version:
for(int i = 0; i < id.length; i++)
{
iz[i] = 1; // RIGHT
id[i] = i;
}
iz[i] is the number of elements for a tree rooted at i (or if i is not a root then iz[i] is undefined). So it should be initialized to 1, not i. Initially each element is a seperate "singleton" tree of size 1.
这篇关于加权快速联盟与路径的COM pression算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
