Kruskal算法
偽代碼：
T=(V,X）炕矮；
while（T中所含邊數(shù)<n-1）
{
從E中選取當(dāng)前權(quán)值最小的邊(u,v);
從E中刪除邊(u,v);
if(邊（u，v）的兩個頂點落在兩個不同的連通分量上）
將邊（u仁连，v）并入T中创肥；
}
并查集:
void UFset() //初始化
{
for（int i=0;i<N;i++）
parent[i]=-1;
}
int Find(int x)
{
int s;//查找位置
//一直查找到parent[s]為負(fù)數(shù)（此時的s即為根節(jié)點）為止
for(s=x;parent[s]>=0;s=parent[s])
while(s!=x)
{
int tmp=parent[x];
parent[x]=s;
s=tmp;
}
return s;
}
void Union(int R1,int R2)
{
//r1為R1的根節(jié)點矿酵，r2為R2的根節(jié)點
int r1=Find(R1),r2=Find(R2);
int tmp=parent[r1]+parent[r2]; //兩個集合接點個數(shù)之后（負(fù)數(shù)）
//如果R2所在樹節(jié)點個數(shù)>R1樹節(jié)點個數(shù)（parent[r1]和parent[r2]均為負(fù)數(shù)）
if（parent[r1]>parent[r2]）
{
parent[r1]=r2;
parent[r2]=tmp;
}
else
{
parent[r2]=r1;
parent[r1]=tmp;
}
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
