本页使用了标题或全文手工转换

普林姆算法

维基百科,自由的百科全书
(重定向自普里姆算法
跳到导航 跳到搜索

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

描述[编辑]

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

  1. 输入:一个加权连通图,其中顶点集合为,边集合为
  2. 初始化:,其中为集合中的任一节点(起始点),
  3. 重复下列操作,直到
    1. 在集合中选取权值最小的边,其中为集合中的元素,而则是中没有加入的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
    2. 加入集合中,将加入集合中;
  4. 输出:使用集合来描述所得到的最小生成树。

时间复杂度[编辑]

最小边、权的数据结构 时间复杂度(总计)
邻接矩阵、搜索
二叉堆(后文伪代码中使用的数据结构)、邻接表
斐波那契堆邻接表

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

例示[编辑]

图例 说明 不可选 可选 已选
Prim Algorithm 0.svg 此为原始的加权连通图。每条边一侧的数字代表其权值。 - - -
Prim Algorithm 1.svg 顶点D被任意选为起始点。顶点ABEF通过单条边与D相连。A是距离D最近的顶点,因此将A及对应边AD以高亮表示。 C, G A, B, E, F D
Prim Algorithm 2.svg 下一个顶点为距离DA最近的顶点。BD为9,距A为7,ED為15,FD為6。因此,FDA最近,因此将顶点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 在当前情况下,可以在CEG间进行选择。CB为8,EB为7,GF为11。E最近,因此将顶点E与相应边BE高亮表示。 C, E, G A, D, F, B
Prim Algorithm 5.svg 这里,可供选择的顶点只有CGCE为5,GE为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語言程序[编辑]

部分主程序段:

 1 procedure prim(v0:integer);
 2 var
 3    lowcost,closest:array[1..maxn] of integer;
 4    i,j,k,min,ans:integer;
 5 
 6    for i:=1 to n do
 7     begin
 8      lowcost[i]:=cost[v0,i];
 9      closest[i]:=v0;
10    end;
11    for i:=1 to n-1 do
12      begin
13       min:=maxint;
14       for j:=1 to n do
15          if (lowcost[j]<min) and (lowcost[j]<>0) then
16           begin
17             min:=lowcost[j];
18             k:=j;
19          end;
20       inc(ans, lowcost[k]);
21       lowcost[k]:=0;
22       for j:=1 to n do
23          if cost[k,j]<lowcost[j] then
24           begin
25             lowcost[j]:=cost[k,j];
26             closest[j]:=k;
27          end;
28    end;
29  writeln(ans);
30 end;

C语言代码[编辑]

 1 //来源:严蔚敏 吴伟民《数据结构(C语言版)》
 2 
 3 void MiniSpanTree_PRIM (MGraph G, VertexType u) {
 4     /*  用普利姆算法從第u個頂點出發構造網G 的最小生成樹T,輸出T的各條邊。
 5         記錄從頂點集U到V-U的代價最小的邊的輔助數組定義:
 6         struct
 7         {
 8             VertexType adjvex;
 9             VRtype lowcost;
10         }closedge[MAX_VERTEX_NUM];
11     */
12     
13     k = LocateVex(G, u);
14     for (j = 0 ; j < G.vexnum; j++) {           //輔助數組初始化
15         if (j != k)
16             closedge[j] = {u, G.arcs[k][j].adj}; //{adjvex, lowcost}
17     }
18     closedge[k].lowcost = 0;                 //初始,U={u}
19     for (i = 1; i < G.vexnum ; i++) {           //選擇其餘G.vexnum -1 個頂點
20         k = minimum(closedge);              //求出T的下個結點:第k結點
21         //  此时 closedge[k].lowcost = MIN{ closedge[Vi].lowcost|closedge[Vi].lowcost>0,Vi∈V-U}
22         printf(closedge[k].adjvex, G.vexs[k]);    //輸出生成樹的邊
23         closedge[k].lowcost = 0;             //第k條邊併入U集
24         for (j = 0; j < G.vexnum; j++) {
25         
26             //新頂點併入U後重新選擇最小邊
27             if (G.arcs[k][j].adj < closedge[j].lowcost && closedge[j].lowcost!=0) 
28                 closedge[j] = {G.vex[k], G.arcs[k][j].adj};
29         }
30     }
31 }
 1 //来源: 浙大-陈越 《数据结构》
 2 
 3 #define ERROR -1
 4 Vertex FindMinDist( MGraph Graph, WeightType dist[] )
 5 {
 6     /* 返回未被收录顶点中dist最小者 */
 7     
 8     Vertex MinV, V;
 9     WeightType MinDist = INFINITY;
10 
11     for (V=0; V<Graph->Nv; V++) {
12         if ( dist[V]!=0 && dist[V]<MinDist) {
13             /* 若V未被收录,且dist[V]更小 */
14             MinDist = dist[V]; /* 更新最小距离 */
15             MinV = V; /* 更新对应顶点 */
16         }
17     }
18     if (MinDist < INFINITY) /* 若找到最小dist */
19         return MinV; /* 返回对应的顶点下标 */
20     else return ERROR;  /* 若这样的顶点不存在,返回-1作为标记 */
21 }
22 
23 int Prim( MGraph Graph, LGraph MST )
24 { /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */
25     WeightType dist[MaxVertexNum], TotalWeight;
26     Vertex parent[MaxVertexNum], V, W;
27     int VCount;
28     Edge E;
29 
30     /* 初始化。默认初始点下标是0 */
31        for (V=0; V<Graph->Nv; V++) {
32         /* 这里假设若V到W没有直接的边,则Graph->G[V][W]定义为INFINITY */
33            dist[V] = Graph->G[0][V];
34            parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */
35     }
36     TotalWeight = 0; /* .
37 
38     ..........初始化权重和     */
39     VCount = 0;      /* 初始化收录的顶点数 */
40     /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
41     MST = CreateGraph(Graph->Nv);
42     E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */
43 
44     /* 将初始点0收录进MST */
45     dist[0] = 0;
46     VCount ++;
47     parent[0] = -1; /* 当前树根是0 */
48 
49     while (1) {
50         V = FindMinDist( Graph, dist );
51         /* V = 未被收录顶点中dist最小者 */
52         if ( V==ERROR ) /* 若这样的V不存在 */
53             break;   /* 算法结束 */
54 
55         /* 将V及相应的边<parent[V], V>收录进MST */
56         E->V1 = parent[V];
57         E->V2 = V;
58         E->Weight = dist[V];
59         InsertEdge( MST, E );
60         TotalWeight += dist[V];
61         dist[V] = 0;
62         VCount++;
63 
64         for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
65             if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
66             /* 若W是V的邻接点并且未被收录 */
67                 if ( Graph->G[V][W] < dist[W] ) {
68                 /* 若收录V使得dist[W]变小 */
69                     dist[W] = Graph->G[V][W]; /* 更新dist[W] */
70                     parent[W] = V; /* 更新树 */
71                 }
72             }
73     } /* while结束*/
74     if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
75        TotalWeight = ERROR;
76     return TotalWeight;   /* 算法执行完毕,返回最小权重和或错误标记 */
77 }

Python语言实现[编辑]

此份源码使用了堆优化

 1 from queue import PriorityQueue as priority_queue
 2 from math import inf
 3 class Node:
 4     def __init__(self,id,**kwargs):
 5         self.id = id
 6         self.fst = self.lst = None
 7 
 8     def __iter__(self):
 9         return NodeIterator(self)
10 
11     def __repr__(self):
12         return "Node(%d)"%self.id
13 
14 class NodeIterator:
15     def __init__(self,Node):
16         self.prst = Node.fst
17 
18     def __next__(self):
19         if self.prst == None:
20             raise StopIteration()
21         ret = self.prst
22         self.prst = self.prst.nxt
23         return ret
24 
25 class Edge:
26     def __init__(self,fr,to,**kwargs):
27         if fr.fst == None:
28             fr.fst = self
29         else:
30             fr.lst.nxt = self
31         fr.lst = self
32         self.to = to
33         self.nxt = None
34         self.w = 1 if 'w' not in kwargs else kwargs['w']
35 
36     def __repr__(self):
37         return "Edge({},{},w = {})",format(self.fr,self.to,self.w)
38 
39 class Graph:
40     def __init__(self,V):
41         self.nodecnt = V
42         self.nodes = [Node(i) for i in range(V)]
43         self.edges = []
44 
45     def add(self,u,v,**kwargs):
46         self.edges.append(Edge(self.nodes[u],self.nodes[v],**kwargs))
47 
48     def MST_prim(self,begin):
49         '''
50         prim algorithm on a graph(with heap),
51         returns the weight sum of the tree
52         or -1 if impossible
53         '''
54         q = priority_queue()
55         vis = [False for _ in range(self.nodecnt)]
56         q.put((0,begin))
57         ret = 0
58         while not q.empty():
59             prst = q.get()
60             if vis[prst[1]]:
61                 continue
62             vis[prst[1]] = True
63             ret += prst[0]
64             for i in self.nodes[prst[1]]:
65                 if not vis[i.to.id]:
66                     q.put((i.w,i.to.id))
67         if all(vis):
68             return ret
69         else:
70             return -1

Java语言实现[编辑]

 1 import java.util.ArrayList;
 2 import java.util.Iterator;
 3 import java.util.List;
 4 
 5 public class Prim {
 6     public static List<Vertex> vertexList = new ArrayList<Vertex>();//结点集
 7     public static List<Edge> EdgeQueue = new ArrayList<Edge>();//边集
 8     public static List<Vertex> newVertex = new ArrayList<Vertex>();//已经 访问过的结点
 9 
10     public static void main(String[] args) {
11         primTree();
12     }
13     public static void buildGraph() {
14         Vertex v1 = new Vertex("a");
15         Prim.vertexList.add(v1);
16         Vertex v2 = new Vertex("b");
17         Prim.vertexList.add(v2);
18         Vertex v3 = new Vertex("c");
19         Prim.vertexList.add(v3);
20         Vertex v4 = new Vertex("d");
21         Prim.vertexList.add(v4);
22         Vertex v5 = new Vertex("e");
23         Prim.vertexList.add(v5);
24         addEdge(v1, v2, 6);
25         addEdge(v1, v3, 7);
26         addEdge(v2, v3, 8);
27         addEdge(v2, v5, 4);
28         addEdge(v2, v4, 5);
29         addEdge(v3, v4, 3);
30         addEdge(v3, v5, 9);
31         addEdge(v5, v4, 7);
32         addEdge(v5, v1, 2);
33         addEdge(v4, v2, 2);
34     }
35     public static void addEdge(Vertex a, Vertex b, int w) {
36         Edge e = new Edge(a, b, w);
37         Prim.EdgeQueue.add(e);
38     }
39     public static void primTree() {
40         buildGraph();
41         Vertex start = vertexList.get(0);
42         newVertex.add(start);
43         for (int n = 0; n < vertexList.size() - 1; n++) {
44             Vertex temp = new Vertex(start.key);
45             Edge tempedge = new Edge(start, start, 1000);
46             for (Vertex v : newVertex) {
47                 for (Edge e : EdgeQueue) {
48                     if (e.start == v && !containVertex(e.end)) {
49                         if (e.key < tempedge.key) {
50                             temp = e.end;
51                             tempedge = e;
52                         }
53                     }
54                 }
55             }
56             newVertex.add(temp);
57         }
58         Iterator it = newVertex.iterator();
59         while (it.hasNext()) {
60             Vertex v = (Vertex) it.next();
61             System.out.println(v.key);
62         }
63     }
64     public static boolean containVertex(Vertex vte) {
65         for (Vertex v : newVertex) {
66             if (v.key.equals(vte.key))
67                 return true;
68         }
69         return false;
70     }
71 }
72 
73 class Vertex {
74     String key;
75     Vertex(String key) {
76         this.key = key;
77     }
78 }
79 
80 class Edge {
81     Vertex start;
82     Vertex end;
83     int key;
84     Edge(Vertex start, Vertex end, int key) {
85         this.start = start;
86         this.end  = end;
87         this.key = key;
88     }
89 }

參考[编辑]

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