普里姆算法（）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家发现；并在1957年由美国计算机科学家羅伯特·C·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
描述
从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：V_{\text{new}}=\{x\}，其中x为集合V中的任一节点（起始点），E_{\text{new}}=\{\}；
重复下列操作，直到V_{\text{new}}=V：
在集合E中选取权值最小的边(u,v)，其中u为集合V_{\text{new}}中的元素，而v则是V中没有加入V_{\text{new}}的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
将v加入集合V_{\text{new}}中，将(u,v)加入集合E_{\text{new}}中；
输出：使用集合V_{\text{new}}和E_{\text{new}}来描述所得到的最小生成树。
时间复杂度
通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O(|V|^2)的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(|E| \log |V|)，其中|E|为连通图的边集大小，|V|为点集大小。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(|E| + |V| \log |V|)，这在连通图足够密集时（当|E|满足\Omega(|V|\log |V|)条件时），可较显著地提高运行速度。
例示
证明
已知图G的边数量为numEdge, 顶点数量为numVert, prim生成的树为T0, 最小生成树（MST）为Tmin
则有，cost(Tmin)0)
设：
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]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]
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 0,Vi∈V-U}
printf(closedge[k].adjvex, G.vexs[k]); //輸出生成樹的邊
closedge[k].lowcost = 0; //第k條邊併入U集
for (j = 0; j
//来源： 浙大-陈越 《数据结构》
#define ERROR -1
Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{
/ 返回未被收录顶点中dist最小者 /
Vertex MinV, V;
WeightType MinDist = INFINITY;
for (V=0; VNv; V++) {
if ( dist[V]!=0 && dist[V]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及相应的边收录进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; WNv; W++ ) / 对图中的每个顶点W /
if ( dist[W]!=0 && Graph->G[V][W]G[V][W] G[V][W]; / 更新dist[W] /
parent[W] = V; / 更新树 /
}
}
} / while结束/
if ( VCount 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
參考
普林演算法與迪科斯彻演算法的策略相似。
评论 (0)