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

目录 1 描述 2 时间复杂度 3 例示 4 证明 5 各语言程序代码 5.1 Pascal语言程序 5.2 C语言代码 5.3 Python语言实现 5.4 Java语言实现 6 参考描述从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

输入：一个加权连通图，其中顶点集合为 � V，边集合为 � E；初始化： � new

{ � } {\displaystyle V_{\text{new}}={x}}，其中 � x为集合 � V中的任一节点（起始点）， � new

{ } {\displaystyle E_{\text{new}}={}}；重复下列操作，直到 � new

� {\displaystyle V_{\text{new}}=V}：在集合 � E中选取权值最小的边 ( � , � ) (u,v)，其中 � u为集合 � new {\displaystyle V_{\text{new}}}中的元素，而 � v则是 � V中没有加入 � new {\displaystyle V_{\text{new}}}的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；将 � v加入集合 � new {\displaystyle V_{\text{new}}}中，将 ( � , � ) (u,v)加入集合 � new {\displaystyle E_{\text{new}}}中；输出：使用集合 � new {\displaystyle V_{\text{new}}}和 � new {\displaystyle E_{\text{new}}}来描述所得到的最小生成树。时间复杂度最小边、权的数据结构时间复杂度（总计）邻接矩阵、搜索 � ( | � | 2 ) O(|V|^{2}) 二叉堆（后文伪代码中使用的数据结构）、邻接表 � ( ( | � | + | � | ) log ⁡ | � | )

� ( | � | log ⁡ | � | ) {\displaystyle O((|V|+|E|)\log |V|)=O(|E|\log |V|)} 斐波那契堆、邻接表 � ( | � | + | � | log ⁡ | � | ) {\displaystyle O(|E|+|V|\log |V|)} 通过邻接矩阵图表示的简易实现中，找到所有最小权边共需 � ( | � | 2 ) O(|V|^{2})的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为 � ( | � | log ⁡ | � | ) {\displaystyle O(|E|\log |V|)}，其中 | � | |E|为连通图的边集大小， | � | |V|为点集大小。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为 � ( | � | + | � | log ⁡ | � | ) {\displaystyle O(|E|+|V|\log |V|)}，这在连通图足够密集时（当 | � | |E|满足 Ω ( | � | log ⁡ | � | ) {\displaystyle \Omega (|V|\log |V|)}条件时），可较显著地提高运行速度。

例示图例说明不可选可选已选 Prim Algorithm 0.svg 此为原始的加权连通图。每条边一侧的数字代表其权值。 - - - Prim Algorithm 1.svg 顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。 C, G A, B, E, F D Prim Algorithm 2.svg 下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E距D为15，F距D为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。 C, G B, E, F A, D Prim Algorithm 3.svg 算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。 C B, E, G A, D, F Prim Algorithm 4.svg 在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E最近，因此将顶点E与相应边BE高亮表示。无 C, E, G A, D, F, B Prim Algorithm 5.svg 这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。无 C, G A, D, F, B, E Prim Algorithm 6.svg 顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。无 G A, D, F, B, E, C Prim Algorithm 7.svg 现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。无无 A, D, F, B, E, C, G 证明已知图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 且以vs为顶点的边，记为 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是最小生成树，得证.

各语言程序代码 Pascal语言程序部分主程序段：

procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min,ans:integer;

for i:=1 to n do begin lowcost[i]:=cost[v0,i]; closest[i]:=v0; end; for i:=1 to n-1 do begin min:=maxint; for j:=1 to n do if (lowcost[j]<min) and (lowcost[j]<>0) then begin min:=lowcost[j]; k:=j; end; inc(ans, lowcost[k]); lowcost[k]:=0; for j:=1 to n do if cost[k,j]<lowcost[j] then begin lowcost[j]:=cost[k,j]; closest[j]:=k; end; end; writeln(ans); end; 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++) {
    
        //新頂點併入U後重新選擇最小邊
        if (G.arcs[k][j].adj < closedge[j].lowcost && closedge[j].lowcost!=0) 
            closedge[j] = {G.vex[k], G.arcs[k][j].adj};
    }
}

} //来源：浙大-陈越《数据结构》

#define ERROR -1 Vertex FindMinDist( MGraph Graph, WeightType dist[] ) { /* 返回未被收录顶点中dist最小者 */

Vertex MinV, V;
WeightType MinDist = INFINITY;

for (V=0; V<Graph->Nv; V++) {
    if ( dist[V]!=0 && dist[V]<MinDist) {
        /* 若V未被收录，且dist[V]更小 */
        MinDist = dist[V]; /* 更新最小距离 */
        MinV = V; /* 更新对应顶点 */
    }
}
if (MinDist < INFINITY) /* 若找到最小dist */
    return MinV; /* 返回对应的顶点下标 */
else return ERROR;  /* 若这样的顶点不存在，返回-1作为标记 */

}

int Prim( MGraph Graph, LGraph MST ) { /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */ WeightType dist[MaxVertexNum], TotalWeight; Vertex parent[MaxVertexNum], V, W; int VCount; Edge E;

/* 初始化。默认初始点下标是0 */
   for (V=0; V<Graph->Nv; V++) {
    /* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */
       dist[V] = Graph->G[0][V];
       parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */
}
TotalWeight = 0; /* .

..........初始化权重和     */
VCount = 0;      /* 初始化收录的顶点数 */
/* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
MST = CreateGraph(Graph->Nv);
E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */

/* 将初始点0收录进MST */
dist[0] = 0;
VCount ++;
parent[0] = -1; /* 当前树根是0 */

while (1) {
    V = FindMinDist( Graph, dist );
    /* V = 未被收录顶点中dist最小者 */
    if ( V==ERROR ) /* 若这样的V不存在 */
        break;   /* 算法结束 */

    /* 将V及相应的边<parent[V], V>收录进MST */
    E->V1 = parent[V];
    E->V2 = V;
    E->Weight = dist[V];
    InsertEdge( MST, E );
    TotalWeight += dist[V];
    dist[V] = 0;
    VCount++;

    for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
        if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
        /* 若W是V的邻接点并且未被收录 */
            if ( Graph->G[V][W] < dist[W] ) {
            /* 若收录V使得dist[W]变小 */
                dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                parent[W] = V; /* 更新树 */
            }
        }
} /* while结束*/
if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
   TotalWeight = ERROR;
return TotalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */

} Python语言实现此份源码使用了堆优化

from queue import PriorityQueue as priority_queue from math import inf class Node: def init(self,id,**kwargs): self.id = id self.fst = self.lst = None

def __iter__(self):
    return NodeIterator(self)

def __repr__(self):
    return "Node(%d)"%self.id

class NodeIterator: def init(self,Node): self.prst = Node.fst

def __next__(self):
    if self.prst == None:
        raise StopIteration()
    ret = self.prst
    self.prst = self.prst.nxt
    return ret

class Edge: def init(self,fr,to,**kwargs): if fr.fst == None: fr.fst = self else: fr.lst.nxt = self fr.lst = self self.to = to self.nxt = None self.w = 1 if 'w' not in kwargs else kwargs['w']

def __repr__(self):
    return "Edge({},{},w = {})",format(self.fr,self.to,self.w)

class Graph: def init(self,V): self.nodecnt = V self.nodes = [Node(i) for i in range(V)] self.edges = []

def add(self,u,v,**kwargs):
    self.edges.append(Edge(self.nodes[u],self.nodes[v],**kwargs))

def MST_prim(self,begin):
    '''
    prim algorithm on a graph(with heap),
    returns the weight sum of the tree
    or -1 if impossible
    '''
    q = priority_queue()
    vis = [False for _ in range(self.nodecnt)]
    q.put((0,begin))
    ret = 0
    while not q.empty():
        prst = q.get()
        if vis[prst[1]]:
            continue
        vis[prst[1]] = True
        ret += prst[0]
        for i in self.nodes[prst[1]]:
            if not vis[i.to.id]:
                q.put((i.w,i.to.id))
    if all(vis):
        return ret
    else:
        return -1

Java语言实现 import java.util.ArrayList; import java.util.Iterator; import java.util.List;

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

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; } }

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为:

普里姆算法

输入：一个加权连通图，其中顶点集合为 � V，边集合为 � E； 初始化： � new

{ � } {\displaystyle V_{\text{new}}={x}}，其中 � x为集合 � V中的任一节点（起始点）， � new

{ } {\displaystyle E_{\text{new}}={}}； 重复下列操作，直到 � new

输入：一个加权连通图，其中顶点集合为 � V，边集合为 � E；初始化： � new

{ } {\displaystyle E_{\text{new}}={}}；重复下列操作，直到 � new