普林姆算法

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

描述

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

1. 输入：一个加权连通图，其中顶点集合为${\displaystyle V}$ ，边集合为${\displaystyle E}$ ；
2. 初始化：${\displaystyle V_{\text{new}}=\{x\}}$ ，其中${\displaystyle x}$ 为集合${\displaystyle V}$ 中的任一节点（起始点），${\displaystyle E_{\text{new}}=\{\}}$ ；
3. 重复下列操作，直到${\displaystyle V_{\text{new}}=V}$ ：
   1. 在集合${\displaystyle E}$ 中选取权值最小的边${\displaystyle (u,v)}$ ，其中${\displaystyle u}$ 为集合${\displaystyle V_{\text{new}}}$ 中的元素，而${\displaystyle v}$ 则是${\displaystyle V}$ 中没有加入${\displaystyle V_{\text{new}}}$ 的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将${\displaystyle v}$ 加入集合${\displaystyle V_{\text{new}}}$ 中，将${\displaystyle (u,v)}$ 加入集合${\displaystyle E_{\text{new}}}$ 中；
4. 输出：使用集合${\displaystyle V_{\text{new}}}$ 和${\displaystyle E_{\text{new}}}$ 来描述所得到的最小生成树。

时间复杂度

最小边、权的数据结构	时间复杂度（总计）
邻接矩阵、搜索	${\displaystyle O(|V|^{2})}$
二叉堆（后文伪代码中使用的数据结构）、邻接表	${\displaystyle O((|V|+|E|)\log |V|)=O(|E|\log |V|)}$
斐波那契堆、邻接表	${\displaystyle O(|E|+|V|\log |V|)}$

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

例示

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

证明

已知图G的边数量为numEdge, 顶点数量为numVert, prim生成的树为T₀, 最小生成树（MST）为T_min

则有，cost(T_min)<=cost(T₀)

设： T₀ 的 numVert-1 条边按照权重由小到大排列依次为：e_k1, e_k2, e_k3, ..., e_kn

T_min 的 numVert-1 条边按照权重由小到大排列依次为：e_g1, e_g2, e_g3, ..., e_gn

其中n=numVert-1

两棵树的边从小到大权重比较，设第一个属于 T₀ 但不属于 T_min 的边为 e_d1, 连接该边的两个顶点为 (v_s, v_e1)

同时存在第一个属于 T_min 但不属于 T₀ 且以v_s为顶点的边，记为 e_d2, 连接该边的两个顶点为 (v_s, v_e2)。

两个边的起点相同。由Prim算法性质可知，w(e_d2) >= w(e_d1)

此时，在 T_min 中删除 e_d2 ，添加 e_d1，边的数量和顶点数量均不变，且不存在环，因此得到新的生成树T_new,且cost(T_min)>=cost(T_new)

又因为 T_min 是MST 所以 cost(T_min)=cost(T_new)。

以此类推，cost(T_min)=cost(T₀)

T₀是最小生成树， 得证.

各語言程序代码

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

參考

普林演算法與迪科斯彻演算法的策略相似。