普林演算法
| 圖與樹 搜索演算法 |
|---|
| 分類 |
| 相關主題 |
普林演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖裏的所有頂點，且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克發現；並在1957年由美國計算機科學家羅伯特·普林獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普林演算法又被稱為DJP演算法、亞爾尼克演算法或普林－亞爾尼克演算法。
描述
從單一頂點開始，普林演算法按照以下步驟逐步擴大樹中所含頂點的數目，直到遍及連通圖的所有頂點。
- 輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；
- 初始化：Vnew = {x}，其中x為集合V中的任一節點（起始點），Enew = {}；
- 重複下列操作，直到Vnew = V：
- 在集合E中選取權值最小的邊（u, v），其中u為集合Vnew中的元素，而v則是V中沒有加入Vnew的頂點（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；
- 將v加入集合Vnew中，將（u, v）加入集合Enew中；
- 輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。
時間複雜度
| 最小邊、權的數據結構 | 時間複雜度（總計） |
|---|---|
| 鄰接矩陣、搜索 | O(V2) |
| 二叉堆（後文偽代碼中使用的數據結構）、鄰接表 | O((V + E) log(V)) = O(E log(V)) |
| 斐波那契堆、鄰接表 | O(E + V log(V)) |
通過鄰接矩陣圖表示的簡易實現中，找到所有最小權邊共需O（V2）的運行時間。使用簡單的二叉堆與鄰接表來表示的話，普林演算法的運行時間則可縮減為O(E log V)，其中E為連通圖的邊數，V為頂點數。如果使用較為複雜的斐波那契堆，則可將運行時間進一步縮短為O(E + V log V)，這在連通圖足夠密集時（當E滿足Ω（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為15，F為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 |
證明
設prim生成的樹為G0
假設存在Gmin使得cost(Gmin)<cost(G0)
則在Gmin中存在(u,v)不屬於G0
將(u,v)加入G0中可得一個環，且(u,v)不是該環的最長邊
這與prim每次生成最短邊矛盾
故假設不成立，得證.
各語言程序代碼
Pascal語言程序
部分主程序段：
procedure prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min,ans:integer;
begin
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++)
{
if ( G.arcs[k][j].adj < closedge[j].lowcost) //新頂點併入U後重新選擇最小邊
closedge[j] = {G.vex[k],G.arcs[k][j].adj};
}
}
}
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;
}
}
參考
普林演算法與迪科斯徹演算法的策略相似。