普里姆算法

普利姆算法主要用来在连通图中找一个最小生成树。

普利姆算法与克鲁斯卡尔算法不一样的地方在于，普利姆算法是从一个点出发，选择距离这个点权值最小的边，而克鲁斯卡尔算法是将边的权值排序，选择出最小的边。

伪算法

            
                Input E, V
                start: x
                Enew = {}, Vnew = {x}
                dst = 0
                while Vnew != V
                {
                    Vcur = Vnew[0]
                    Ecur = getMin(E, Vcur)
                    dst += Ecur.value
                    Vnew.append(Ecur.v)
                    Enew.append(Ecur)
                }
            
        

流程演示

有一个这样的图。

算法的流程为:
从 A 出发, 此时 Enew = {}, Vnew = {A} dst = 0

        
            1.  可选 B F
                · 选择 F 距离 A 最近选择 F
            2.  可选 B, D, G
                · 选择 D，因为 D 距离 {A,F} 中的 F 最近。
            3.  可选 B, G, E
                · 选择 B， B 距离 {A,F,D}中的 F 最近
            4.  可选 E, G
                · 选择 E
            5.  可选 G
                · 选择 G