普林姆算法

證明

已知圖G的邊數量為numEdge, 頂點數量為numVert, prim生成的樹為T₀, 最小生成樹（MST）為Tₘᵢₙ
則有，cost(Tₘᵢₙ)<=cost(T₀)
設：
T₀ 的 numVert-1 條邊按照權重由小到大排列依次為：eₖ₁, eₖ₂, eₖ₃, ..., eₖₙ
Tₘᵢₙ 的 numVert-1 條邊按照權重由小到大排列依次為：eg₁, eg₂, eg₃, ..., egₙ
其中n=numVert-1
兩棵樹的邊從小到大權重比較，設第一個屬於 T₀ 但不屬於 Tₘᵢₙ 的邊為 ed₁, 連接該邊的兩個頂點為 (vₛ, vₑ₁)
同時存在第一個屬於 Tₘᵢₙ 但不屬於 T₀ 且以vₛ為頂點的邊，記為 ed₂, 連接該邊的兩個頂點為 (vₛ, vₑ₂)。
兩個邊的起點相同。由Prim演算法性質可知，w(ed₂) >= w(ed₁)
此時，在 Tₘᵢₙ 中刪除 ed₂ ，添加 ed₁，邊的數量和頂點數量均不變，且不存在環，因此得到新的生成樹Tnew,且cost(Tₘᵢₙ)>=cost(Tnew)
又因為 Tₘᵢₙ 是MST 所以 cost(Tₘᵢₙ)=cost(Tnew)。
以此類推，cost(Tₘᵢₙ)=cost(T₀)
T₀是最小生成樹， 得證.

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 do12      begin13       min:=maxint;14       for j:=1 to n do15          if (lowcost[j]<min) and (lowcost[j]<>0) then16           begin17             min:=lowcost[j];18             k:=j;19          end;20       inc(ans, lowcost[k]);21       lowcost[k]:=0;22       for j:=1 to n do23          if cost[k,j]<lowcost[j] then24           begin25             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 && closedge[j].lowcost!=0) //新頂點併入U後重新選擇最小邊24                 closedge[j] = {G.vex[k], G.arcs[k][j].adj};25         }26     }27 }
 1 //来源： 浙大-陈越 《数据结构》 2 #define ERROR -1 3 Vertex FindMinDist( MGraph Graph, WeightType dist[] ) 4 { /* 返回未被收录顶点中dist最小者 */ 5     Vertex MinV, V; 6     WeightType MinDist = INFINITY; 7  8     for (V=0; V<Graph->Nv; V++) { 9         if ( dist[V]!=0 && dist[V]<MinDist) {10             /* 若V未被收录，且dist[V]更小 */11             MinDist = dist[V]; /* 更新最小距离 */12             MinV = V; /* 更新对应顶点 */13         }14     }15     if (MinDist < INFINITY) /* 若找到最小dist */16         return MinV; /* 返回对应的顶点下标 */17     else return ERROR;  /* 若这样的顶点不存在，返回-1作为标记 */18 }19 20 int Prim( MGraph Graph, LGraph MST )21 { /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */22     WeightType dist[MaxVertexNum], TotalWeight;23     Vertex parent[MaxVertexNum], V, W;24     int VCount;25     Edge E;26 27     /* 初始化。默认初始点下标是0 */28        for (V=0; V<Graph->Nv; V++) {29         /* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */30            dist[V] = Graph->G[0][V];31            parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */32     }33     TotalWeight = 0; /* .34 35     ..........初始化权重和     */36     VCount = 0;      /* 初始化收录的顶点数 */37     /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */38     MST = CreateGraph(Graph->Nv);39     E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */40 41     /* 将初始点0收录进MST */42     dist[0] = 0;43     VCount ++;44     parent[0] = -1; /* 当前树根是0 */45 46     while (1) {47         V = FindMinDist( Graph, dist );48         /* V = 未被收录顶点中dist最小者 */49         if ( V==ERROR ) /* 若这样的V不存在 */50             break;   /* 算法结束 */51 52         /* 将V及相应的边<parent[V], V>收录进MST */53         E->V1 = parent[V];54         E->V2 = V;55         E->Weight = dist[V];56         InsertEdge( MST, E );57         TotalWeight += dist[V];58         dist[V] = 0;59         VCount++;60 61         for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */62             if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {63             /* 若W是V的邻接点并且未被收录 */64                 if ( Graph->G[V][W] < dist[W] ) {65                 /* 若收录V使得dist[W]变小 */66                     dist[W] = Graph->G[V][W]; /* 更新dist[W] */67                     parent[W] = V; /* 更新树 */68                 }69             }70     } /* while结束*/71     if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */72        TotalWeight = ERROR;73     return TotalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */74 }

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 }