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

普林姆算法

维基百科,自由的百科全书
跳转至: 导航搜索

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

描述[编辑]

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

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

时间复杂度[编辑]

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

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

例示[编辑]

图例 说明 不可选 可选 已选
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,E为15,F为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 的边为 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 begin
 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 void MiniSpanTree_PRIM (MGraph G, VertexType u) {
 3     /*  用普利姆算法從第u個頂點出發構造網G 的最小生成樹T,輸出T的各條邊。
 4         記錄從頂點集U到V-U的代價最小的邊的輔助數組定義:
 5         struct
 6         {
 7             VertexType adjvex;
 8             VRtype lowcost;
 9         }closedge[MAX_VERTEX_NUM];
10     */
11     k = LocateVex(G, u);
12     for (j = 0 ; j < G.vexnum; j++) { //輔助數組初始化
13         if (j != k)
14             closedge[j] = {u, G.arcs[k][j].adj}; //{adjvex, lowcost}
15     }
16     closedge[k].lowcost = 0; //初始,U={u}
17     for (i = 1; i < G.vexnum ; i++) { //選擇其餘G.vexnum -1 個頂點
18         k = minimum(closedge); //求出T的下個結點:第k結點
19         //  此时 closedge[k].lowcost = MIN{ closedge[Vi].lowcost|closedge[Vi].lowcost>0,Vi∈V-U}
20         printf(closedge[k].adjvex, G.vexs[k]); //輸出生成樹的邊
21         closedge[k].lowcost = 0; //第k條邊併入U集
22         for (j = 0; j < G.vexnum; j++) {
23             if (G.arcs[k][j].adj < closedge[j].lowcost) //新頂點併入U後重新選擇最小邊
24                 closedge[j] = {G.vex[k], G.arcs[k][j].adj};
25         }
26     }
27 }

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 }

參考[编辑]

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