JAVA算法3——连通性问题之快速合并算法的加权版本
浏览数：21 /
时间：2015年06月08日
在进行合并操作的时候，我们不是随意的把第二棵树连接到第一棵树，而是记下每棵树的节点数，合并的时候，总是要把结点数较少的树连接到节点数较大的数上。这个改变需要修改的代码稍微多一点，而且还需要一个数组来存放节点数，但是使程序的效率提高不少，我们把这个算法称为“加权快速合并算法”。
public class QuickUW
{
public static void main(String[] args)
{
int N=Integer.parseInt(args[0]);
int id[]=new int[N],sz[]=new int[N];
for(int i=0;i<N;i++)
{
id[i]=i;
sz[i]=1;
}
for(In.init();!In.empty();)
{
int i,j,p=In.getInt(),q=In.getInt();
for(i=p;i!=id[i];i=id[i]);
for(j=q;j!=id[i];j=id[j]);
if(i==j) continue;
if(sz[i]<sz[j])
{
id[i]=j;
sz[j]+=sz[i];
}
else
{
id[j]=i;
sz[j]+=sz[j];
}
}
} 加权快速合并算法所构建的森林，树中的路径比未加权合并算法中树的路径短很多。最坏情况下时，要合并的集合大小总是相等（集合大小是2的幂）。虽然这种树的结构看起来复杂，但他们有一个简单的性质，即在一棵具有2的n次幂结点的树中，要到达树根所需经过的最大的连接数是n。
性质：加权快速合并算法要判断N个对象中的两个对象是否是连接的，至多经过2lgN条连线。
本文出自 “飞鱼技术” 博客，请务必保留此出处http://flyingfish.blog.51cto.com/9580339/1622575
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
