克鲁斯卡尔算法也是一种用来寻找最小生成树的算法。但是与普利姆算法不同的是,它是把边的权值进行排列,每次选取权值最小的边(不会形成环)。
E V
n = V.size()
i = 0
Enew = {}, Vnew = {}
while( i < n )
{
E = sort(E)
Ecur = getMin(E)
if (Ecur.u not in Vnew and Ecur not in Vnew)
{
Enew.append(Ecur)
Vnew.append(Ecur.v)
Vnew.append(Ecur.u)
}
i++
}
1. 最短的边为 (F,D)
2. 最短的边为(A,F),(F,B),任意选择(A,F)
3. 最短的边为(F,B)
4. 最短边为(A,B),(D,E),因为选择 (A,B) 会形成环,所以选择(D,E)
5. 最短边为(F,G)
生成的最小生成树为: