克鲁斯卡尔算法

维基百科

克鲁斯卡尔算法也是一种用来寻找最小生成树的算法。但是与普利姆算法不同的是,它是把边的权值进行排列,每次选取权值最小的边(不会形成环)。

伪算法

            
                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)
            
        
生成的最小生成树为: