Prim最小生成树算法

Prim最小生成树算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

描述

从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
重复下列操作，直到Vnew = V：
在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
将v加入集合Vnew中，将（u, v）加入集合Enew中；
输出：使用集合Vnew和Enew来描述所得到的最小生成树。
时间复杂度
|最小边、权的数据结构|时间复杂度（总计）|
|:—:|:—:|
|邻接矩阵、搜索|O(V²)|
|二叉堆（后文伪代码中使用的数据结构）、邻接表|O((V + E) log(V)) = O(E log(V))|
|斐波那契堆、邻接表|O(E + V log(V))|
证明
已知图G的边数量为numEdge, 顶点数量为numVert, prim生成的树为T0, 最小生成树（MST）为Tmin
则有，cost(Tmin)<=cost(T0)
设： T0 的 numVert-1 条边按照权重由小到大排列依次为：ek1, ek2, ek3, …, ekn
Tmin 的 numVert-1 条边按照权重由小到大排列依次为：eg1, eg2, eg3, …, egn
其中n=numVert-1
两棵树的边从小到大权重比较，设第一个属于 T0 但不属于 Tmin 的边为 ed1, 连接该边的两个顶点为 (vs, ve1)
同时存在第一个属于 Tmin 但不属于 T0 的边为 ed2, 连接该边的两个顶点为 (vs, ve2)。
两个边的起点相同。由Prim算法性质可知，w(ed2) >= w(ed1)
此时，在 Tmin 中删除 ed2 ，添加 ed1，边的数量和顶点数量均不变，且不存在环，因此得到新的生成树Tnew,且cost(Tmin)>=cost(Tnew)
又因为 Tmin 是MST 所以 cost(Tmin)=cost(Tnew)。
以此类推，cost(Tmin)=cost(T0)
T0是最小生成树，得证.

代码

C

//来源：严蔚敏 吴伟民《数据结构(C语言版)》
void MiniSpanTree_PRIM (MGraph G, VertexType u) {
    /*  用普利姆算法從第u個頂點出發構造網G 的最小生成樹T,輸出T的各條邊。
        記錄從頂點集U到V-U的代價最小的邊的輔助數組定義：
        struct
        {
            VertexType adjvex;
            VRtype lowcost;
        }closedge[MAX_VERTEX_NUM];
    */
    k = LocateVex(G, u);
    for (j = 0 ; j < G.vexnum; j++) { //輔助數組初始化
        if (j != k)
            closedge[j] = {u, G.arcs[k][j].adj}; //{adjvex, lowcost}
    }
    closedge[k].lowcost = 0; //初始，U={u}
    for (i = 1; i < G.vexnum ; i++) { //選擇其餘G.vexnum -1 個頂點
        k = minimum(closedge); //求出T的下個結點：第k結點
        //  此时 closedge[k].lowcost = MIN{ closedge[Vi].lowcost|closedge[Vi].lowcost>0,Vi∈V-U}
        printf(closedge[k].adjvex, G.vexs[k]); //輸出生成樹的邊
        closedge[k].lowcost = 0; //第k條邊併入U集
        for (j = 0; j < G.vexnum; j++) {
            if (G.arcs[k][j].adj < closedge[j].lowcost) //新頂點併入U後重新選擇最小邊
                closedge[j] = {G.vex[k], G.arcs[k][j].adj};
        }
    }
}

Java

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Prim {
    public static List<Vertex> vertexList = new ArrayList<Vertex>();//结点集
    public static List<Edge> EdgeQueue = new ArrayList<Edge>();//边集
    public static List<Vertex> newVertex = new ArrayList<Vertex>();//已经 访问过的结点

    public static void main(String[] args) {
        primTree();
    }
    public static void buildGraph() {
        Vertex v1 = new Vertex("a");
        Prim.vertexList.add(v1);
        Vertex v2 = new Vertex("b");
        Prim.vertexList.add(v2);
        Vertex v3 = new Vertex("c");
        Prim.vertexList.add(v3);
        Vertex v4 = new Vertex("d");
        Prim.vertexList.add(v4);
        Vertex v5 = new Vertex("e");
        Prim.vertexList.add(v5);
        addEdge(v1, v2, 6);
        addEdge(v1, v3, 7);
        addEdge(v2, v3, 8);
        addEdge(v2, v5, 4);
        addEdge(v2, v4, 5);
        addEdge(v3, v4, 3);
        addEdge(v3, v5, 9);
        addEdge(v5, v4, 7);
        addEdge(v5, v1, 2);
        addEdge(v4, v2, 2);
    }
    public static void addEdge(Vertex a, Vertex b, int w) {
        Edge e = new Edge(a, b, w);
        Prim.EdgeQueue.add(e);
    }
    public static void primTree() {
        buildGraph();
        Vertex start = vertexList.get(0);
        newVertex.add(start);
        for (int n = 0; n < vertexList.size() - 1; n++) {
            Vertex temp = new Vertex(start.key);
            Edge tempedge = new Edge(start, start, 1000);
            for (Vertex v : newVertex) {
                for (Edge e : EdgeQueue) {
                    if (e.start == v && !containVertex(e.end)) {
                        if (e.key < tempedge.key) {
                            temp = e.end;
                            tempedge = e;
                        }
                    }
                }
            }
            newVertex.add(temp);
        }
        Iterator it = newVertex.iterator();
        while (it.hasNext()) {
            Vertex v = (Vertex) it.next();
            System.out.println(v.key);
        }
    }
    public static boolean containVertex(Vertex vte) {
        for (Vertex v : newVertex) {
            if (v.key.equals(vte.key))
                return true;
        }
        return false;
    }
}

class Vertex {
    String key;
    Vertex(String key) {
        this.key = key;
    }
}

class Edge {
    Vertex start;
    Vertex end;
    int key;
    Edge(Vertex start, Vertex end, int key) {
        this.start = start;
        this.end  = end;
        this.key = key;
    }
}

参考资料

维基百科-普林姆算法

描述

时间复杂度

证明

代码

C

Java

参考资料