1. 急！數據結構最小生成樹prim演算法C語言實現
Kruskal演算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化輔助數組
k=1; //k表示當前構造最小生成樹的第幾條邊,初值為1
j=0; //E中邊的下標,初值為0
while (k<n) //生成的邊數小於n時循環
{
m1=E[j].u;m2=E[j].v; //取一條邊的頭尾頂點
sn1=vset[m1];sn2=vset[m2]; //分別得到兩個頂點所屬的集合編號
if (sn1!=sn2) //兩頂點屬於不同的集合,該邊是最小生成樹的一條邊
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成邊數增1
for (i=0;i<n;i++) //兩個集合統一編號
if (vset[i]==sn2) //集合編號為sn2的改為sn1
vset[i]=sn1;
}
j++; //掃描下一條邊
}
}
Prim演算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //給lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1個頂點
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 邊(%d,%d)權為:%d/n",closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<n;j++) //修改數組lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
2. 普里姆演算法
可以這么理解：因為最小生成樹是包含所有頂點的所以開始lowcost先儲存到第一個點的所有值，然後執行下面演算法，找到最小值並記錄是第幾個點，比如說這個點是3，這樣有了一條1-3得道路已經確定，現在從3出發找從3出發到其他頂點的路徑，如果這個從3出發到達的路徑長度比從1出發的短，則更新lowcost，這樣使得lowcost保存一直到達該頂點的最短路徑。比如1-4是5，3-4是4，則lowcost從原來的5被改為4。
3. 用C語言編程，演算法是基於ISLIP的改進演算法PIRM演算法
首先 普里姆演算法 並不是一種交換機調度算粗芹法 是構建一個最小生成樹的演算法
其次 性能拿棗測試分析吞吐量岩敏畢和公平性 這是什麼東西也要說清楚一下
4. 用普里姆演算法求最小生成樹（C++）
求最小生成樹的譜里姆演算法
#include <iostream>
using namespace std;
const int n=6;
const int e=10;
class edgeset
{public :
int front;
int end;
int weight;};
class tree
{public :
int s[n+1][n+1];
edgeset ct[n+1];
void prim(tree &t)
{
int i,j,k,min,t1,m,w;
for(i=1;i<n;i++)
{t.ct[i].front=1;
t.ct[i].end=i+1;
t.ct[i].weight=t.s[1][i+1];}
for(k=2;k<=n;k++)
{min=32767;
m=k-1;
for(j=k-1;j<n;j++)
if(t.ct[j].weight<min)
{min=t.ct[j].weight;
m=j;}
edgeset temp=t.ct[k-1];
t.ct[k-1]=t.ct[m];
t.ct[m]=temp;
j=t.ct[k-1].end;
for(i=k;i<n;i++)
{t1=t.ct[i].end;
w=t.s[j][t1];
if(w<t.ct[i].weight)
{t.ct[i].weight=w;
t.ct[i].front=j;}}}}
};
void main ()
{int j,w;tree t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)t.s[i][j]=0;
else t.s[i][j]=32767;
for(int k=1;k<=e;k++)
{cout<<"輸入一條邊及邊上的權值 ";
cin>>i>>j>>w;
cout<<endl;
t.s[i][j]=w;
t.s[j][i]=w;}
t.prim(t);
for(i=1;i<n;i++)
{cout<<t.ct[i].front<<" "<<t.ct[i].end<<" "<<t.ct[i].weight<<endl;}
}
我們的實驗上機做了的
運行結果
輸入一條邊及邊上的權值 1 2 6
輸入一條邊及邊上的權值 1 3 1
輸入一條邊及邊上的權值 1 4 6
輸入一條邊及邊上的權值 2 3 5
輸入一條邊及邊上的權值 2 5 3
輸入一條邊及邊上的權值 3 4 7
輸入一條邊及邊上的權值 3 5 5
輸入一條邊及邊上的權值 3 6 4
輸入一條邊及邊上的權值 4 6 2
輸入一條邊及邊上的權值 5 6 6
1 3 1
3 6 4
6 4 2
3 5 5
5 2 3
Press any key to continue
你有的圖不一樣就該頂點和邊就是
const int n=6;
const int e=10;
5. 求高手 編程 C語言 謝謝
Prim演算法c++程序：
//MiniSpanTree_Prim.cpp
//This function is to create MiniSpanTree_Prim with Prim Algorithm
# include <iostream>
# include <malloc.h>
# include <空肆滲conio.h>
using namespace std;
# define INFINITY 1000
# define MAX_VERTEX_NUM 20
# define OK 1
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef int EType;
typedef int InfoType;
typedef int VertexType;
typedef int VRType;
typedef int lowcost;
typedef struct //define Closedege structure
{ VertexType adjvex;
VRType lowcost;
}Closedge;
typedef struct ArcCell //define MGraph structure
{ EType adj;
InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{ VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
int CreatUDN(MGraph &G) //CreatUDN() sub-function
{ int IncInfo,i=0,j=0,k,v1,v2,w;
cout<<endl<<"Please input the number of G.vexnum (eg,G.vexnum=4) : ";
cin>>G.vexnum; //input the number of vex
cout<<"Please input the number of G.arcnum (eg,G.arcnum=4) : ";
cin>>G.arcnum; //input the number of arc
for(i=0;i<G.vexnum;++i)
for(j=i;j<G.vexnum;++j)
{ G.arcs[i][j].adj=G.arcs[j][i].adj=INFINITY; //initial weigh
G.arcs[i][j].info=G.arcs[j][i].info=NULL;
}
cout<<"Please input IncInfo (0 for none) : ";
cin>>IncInfo; //if need information, input non-zero
cout<<"Plese input arc(V1-->V2), For example: (V1=1,V2=3),(V1=2,V2=4)..."<<endl;
for(k=0;k<G.arcnum;++k) //斗脊input arc(v1,v2)
{ cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum) : ";
cin>>v1;
cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum) : ";
cin>>v2;
cout<<"Please input the "<<k+1<<"雹閉th arc's weight : ";
cin>>w;
i=v1;
j=v2;
while(i<1||i>G.vexnum||j<1||j>G.vexnum) //if (v1,v2) illegal
{ cout<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum) : ";
cin>>v1;
cout<<"Please input the "<<k+1<<"th arc's v2 (0<v1<G.vexnum) : ";
cin>>v2;
cout<<"Please input the "<<k+1<<"th arc's weight : ";
cin>>w;
i=v1;
j=v2;
} //while end
i--;
j--;
G.arcs[i][j].adj=G.arcs[j][i].adj=w; //
cout<<"G.arcs["<<i+1<<"]["<<j+1<<"].adj=";
cout<<"G.arcs["<<j+1<<"]["<<i+1<<"].adj="<<G.arcs[j][i].adj<<endl;
if(IncInfo)
{ cout<<"Please input the "<<k+1<<"th arc's Info : ";
cin>>*G.arcs[i][j].info; //input information
}
} //for end
return (OK);
} //CreatUDN() end
int Minimum(Closedge *closedge,int Vexnum) //Minimum() sub-function
{ int min=1,j; //return min (closedge[min].lowcost)
if(closedge[min].lowcost==0)
min++; //closedge[min].lowcost!=0
for(j=0;j<Vexnum;++j)
if(closedge[j].lowcost<closedge[min].lowcost
&&closedge[j].lowcost>0)
min=j;
return (min);
} //Minimim() end
int LocatedVex(MGraph G,VertexType u) //LocatedVex() sub-fuction
{ return (u);
}
void MiniSpanTree_Prim(MGraph G,VertexType u) //MiniSpanTree_Prim() sub-function
{ int k,j,i,Vexnum=G.vexnum;
k=LocatedVex(G,u);
Closedge closedge[MAX_VERTEX_NUM];
for(j=0;j<G.vexnum;++j) //initial closedge[]
if(j!=k)
{ closedge[j].adjvex=u; // (u,j)
closedge[j].lowcost=G.arcs[k][j].adj;
}
closedge[k].lowcost=0; //U include k
for(i=1;i<G.vexnum;++i)
{ k=Minimum(closedge,Vexnum); //select k=min(closedge[vi].lowcost)
cout<<endl<<"("<<closedge[k].adjvex+1<<","<<k+1<<")";
cout<<"="<<G.arcs[closedge[k].adjvex][k].adj;
closedge[k].lowcost=0; //U include k
for(j=0;j<G.vexnum;++j) //renew closedge[k]
if(G.arcs[k][j].adj<closedge[j].lowcost)
{ closedge[j].adjvex=k;
closedge[j].lowcost=G.arcs[k][j].adj;
} //if end
} //for end
} //Minimun() end
void main() //main() function
{ MGraph G;
VertexType u=0;
cout<<endl<<endl<<"MiniSpanTree_Prim.cpp";
cout<<endl<<"====================="<<endl;
CreatUDN(G); //call CreatUDN(G) function
cout<<endl<<"The MiniSpanTree_Prim is created as follow order:";
MiniSpanTree_Prim(G,u); //call MiniSpanTree_Prim() function
cout<<endl<<endl<<"...OK!...";
getch();
} //main() end
6. pascal普里姆演算法
Prim演算法用於求無向圖的最小生成樹
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
Prim演算法實現：
（1）集合：設置一個數組set(i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
採用堆可以將復雜度降為O(m log n)，如果採用Fibonaci堆可以將復雜度降為O(n log n + m)
7. 最小生成樹怎麼求
一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，並且有保持圖連通的最少的邊。最小生成樹可以用kruskal（克魯斯卡爾）演算法或Prim（普里姆）演算法求出。
求MST的一般演算法可描述為：針對圖G，從空樹T開始，往集合T中逐條選擇並加入n-1條安全邊（u，v），最終生成一棵含n-1條邊的MST。
當一條邊（u，v）加入T時，必須保證T∪{(u，v)}仍是MST的子集，我們將這樣的邊稱為T的安全邊。
偽代碼
GenerieMST(G){//求G的某棵MST
T〈-￠； //T初始為空，是指頂點集和邊集均空
while T未形成G的生成樹 do{
找出T的一條安全邊（u，v）；//即T∪{(u，v)}仍為MST的子集
T=T∪{(u，v)}； //加入安全邊，擴充T
}
return T； //T為生成樹且是G的一棵MST
}
注意：
下面給出的兩種求MST的演算法均是對上述的一般演算法的求精，兩演算法的區別僅在於求安全邊的方法不同。
為簡單起見，下面用序號0，1，…，n-1來表示頂點集，即是：
V(G)={0，1，…，n-1}，
G中邊上的權解釋為長度，並設T=(U，TE）。
求最小生成樹的具體演算法（pascal):
Prim演算法
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min: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
{尋找離生成樹最近的未加入頂點 k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {將頂點k 加入生成樹}
{生成樹中增加一條新的邊 k 到 closest[k]}
{修正各點的 lowcost 和 closest 值}
for j:=1 to n do
if cost[k,j]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;
Kruskal演算法
按權值遞增順序刪去圖中的邊，若不形成迴路則將此邊加入最小生成樹。
function find(v:integer):integer; {返回頂點 v 所在的集合}
var i:integer;
begin
i:=1;
while (i<=n) and (not v in vset) do inc(i);
if i<=n then find:=i else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=i;{初始化定義 n 個集合，第 I個集合包含一個元素 I}
p:=n-1; q:=1; tot:=0; {p 為尚待加入的邊數，q 為邊集指針}
sort;
{對所有邊按權值遞增排序，存於 e中，e.v1 與 e.v2 為邊 I 所連接的兩個頂點的
序號，e.len 為第 I條邊的長度}
while p>0 do begin
i:=find(e[q].v1）;j:=find(e[q].v2）;
if i<>j then begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
C語言代碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charvexs[MAX_VERTEX_NUM];//節點數組
AdjMatrixarcs;//鄰接矩陣
intvexnum,arcnum;//圖的當前節點數和弧數
}MGraph;
typedefstructPnode//用於普利姆演算法
{
charadjvex;//節點
doublelowcost;//權值
}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點集U到V-U的代價最小的邊的輔助數組定義
typedefstructKnode//用於克魯斯卡爾演算法中存儲一條邊及其對應的2個節點
{
charch1;//節點1
charch2;//節點2
doublevalue;//權值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue);
intLocateVex(MGraphG,charch);
intMinimum(MGraphG,Closedgeclosedge);
voidMiniSpanTree_PRIM(MGraphG,charu);
voidSortdge(Dgevalue&dgevalue,MGraphG);
//-------------------------------------------------------------------------------
intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構造無向加權圖的鄰接矩陣
{
inti,j,k;
cout<<"請輸入圖中節點個數和邊/弧的條數：";
cin>>G.vexnum>>G.arcnum;
cout<<"請輸入節點：";
for(i=0;i<G.vexnum;++i)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)//初始化數組
{
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
}
cout<<"請輸入一條邊依附的定點及邊的權值："<<endl;
for(k=0;k<G.arcnum;++k)
{
cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
i=LocateVex(G,dgevalue[k].ch1）;
j=LocateVex(G,dgevalue[k].ch2）;
G.arcs[i][j].adj=dgevalue[k].value;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
returnOK;
}
intLocateVex(MGraphG,charch)//確定節點ch在圖G.vexs中的位置
{
inta;
for(inti=0;i<G.vexnum;i++)
{
if(G.vexs[i]==ch)
a=i;
}
returna;
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆演算法求最小生成樹
{
inti,j,k;
Closedgeclosedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;j++)
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=Minimum(G,closedge);
cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
{
if(G.arcs[k][j].adj<closedge[j].lowcost)
{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中權值最小的邊，並返回其頂點在vexs中的位置
{
inti,j;
doublek=1000;
for(i=0;i<G.vexnum;i++)
{
if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
{
k=closedge[i].lowcost;
j=i;
}
}
returnj;
}
voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克魯斯卡爾演算法求最小生成樹
{
intp1,p2,i,j;
intbj[MAX_VERTEX_NUM];//標記數組
for(i=0;i<G.vexnum;i++)//標記數組初始化
bj[i]=i;
Sortdge(dgevalue,G);//將所有權值按從小到大排序
for(i=0;i<G.arcnum;i++)
{
p1=bj[LocateVex(G,dgevalue[i].ch1）];
p2=bj[LocateVex(G,dgevalue[i].ch2）];
if(p1!=p2）
{
cout<<"("<<dgevalue[i].ch1<<","<<dgevalue[i].ch2<<","<<dgevalue[i].value<<")"<<endl;
for(j=0;j<G.vexnum;j++)
{
if(bj[j]==p2）
bj[j]=p1;
}
}
}
}
voidSortdge(Dgevalue&dgevalue,MGraphG)//對dgevalue中各元素按權值按從小到大排序
{
inti,j;
doubletemp;
charch1,ch2;
for(i=0;i<G.arcnum;i++)
{
for(j=i;j<G.arcnum;j++)
{
if(dgevalue[i].value>dgevalue[j].value)
{
temp=dgevalue[i].value;
dgevalue[i].value=dgevalue[j].value;
dgevalue[j].value=temp;
ch1=dgevalue[i].ch1;
dgevalue[i].ch1=dgevalue[j].ch1;
dgevalue[j].ch1=ch1;
ch2=dgevalue[i].ch2;
dgevalue[i].ch2=dgevalue[j].ch2;
dgevalue[j].ch2=ch2;
}
}
}
}
voidmain()
{
inti,j;
MGraphG;
charu;
Dgevaluedgevalue;
CreateUDG(G,dgevalue);
cout<<"圖的鄰接矩陣為："<<endl;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
cout<<G.arcs[i][j].adj<<"";
cout<<endl;
}
cout<<"=============普利姆演算法===============\n";
cout<<"請輸入起始點：";
cin>>u;
cout<<"構成最小代價生成樹的邊集為：\n";
MiniSpanTree_PRIM(G,u);
cout<<"============克魯斯科爾演算法=============\n";
cout<<"構成最小代價生成樹的邊集為：\n";
MiniSpanTree_KRSL(G,dgevalue);
}
pascal演算法
program didi;
var
a:array[0..100000] of record
s,t,len:longint;
end;
fa,r:array[0..10000] of longint;
n,i,j,x,y,z:longint;
tot,ans:longint;
count,xx:longint;
procere quick(l,r:longint);
var
i,j,x,y,t:longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2].len;
repeat
while x>a[i].len do inc(i);
while x<a[j].len do dec(j);
if i<=j then
begin
y:=a[i].len;a[i].len:=a[j].len;a[j].len:=y;
y:=a[i].s;a[i].s:=a[j].s;a[j].s:=y;
y:=a[i].t;a[i].t:=a[j].t;a[j].t:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then quick(i,r);
if l<j then quick(l,j);
end;
function find(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=find(fa[x]);
find:=fa[x];
end;
procere union(x,y:longint);{啟發式合並}
var
t:longint;
begin
x:=find(x);
y:=find(y);
if r[x]>r[y] then
begin
t:=x;x:=y;y:=t;
end;
if r[x]=r[y] then inc(r[x]);
fa[x]:=y;
end;
begin
readln(xx,n);
for i:=1 to xx do fa[i]:=i;
for i:=1 to n do
begin
read(x,y,z);
inc(tot);
a[tot].s:=x;
a[tot].t:=y;
a[tot].len:=z;
end;
quick（1,tot);{將邊排序}
ans:=0;
count:=0;
i:=0;
while count<=x-1 do{count記錄加邊的總數}
begin
inc(i);
with a[i] do
if find(s)<find(t) then
begin
union(s,t);
ans:=ans+len;
inc(count);
end;
end;
write(ans);
end.
Prim
var
m,n:set of 1..100;
s,t,min,x,y,i,j,k,l,sum,p,ii:longint;
a:array[1..100,1..100]of longint;
begin
readln(p);
for ii:=1 to p do
begin
k:=0; sum:=0;
fillchar(a,sizeof(a),255);
readln(x);
m:=[1];
n:=[2..x];
for i:=1 to x do
begin
for j:=1 to x do
begin
read(a[i,j]);
if a[i,j]=0
then a[i,j]:=maxlongint;
end;
readln;
end;
for l:=1 to x-1 do
begin
min:=maxlongint;
for i:=1 to x do
if i in m
then begin
for j:=1 to x do
begin
if (a[i,j]<min)and(j in n)
then begin
min:=a[i,j];
s:=i;
t:=j;
end;
end;
end;
sum:=sum+min;
m:=m+[t];
n:=n-[t];
inc(k);
end;
writeln(sum);
end;
end.
8. 求一個學過數據結構（C語言版）的大神，有一個關於克魯斯卡爾演算法和普里姆演算法的問題！
克魯斯卡爾和prime演算法都是最小生成樹的貪心演算法，可以證明其擁有最優解結構。證明簡單的可以參考wiki，要嚴格證明請參襲虛考演算法導論和計算機程序設返禪信計的藝術中的相關內容。由於其相關論文比較久遠，我也不建議你去查了漏輪。
9. 普里姆演算法(Prime)
普利姆(Prim)演算法求最小生成樹，也就是在包含 n 個頂點的連通圖中，找出只有(n-1)條邊包含所有 n 個頂點的連通子圖，也就是所謂的極小連通子圖
普利坦鬧仔姆的演算法如下:
1. 有七個站點 A,B,C,D,E,F,G，現在需要修線路把彎嘩七個站點聯通
2. 各個站點的距離用邊線表示(權)，比如 A->C 為7公里
問： 如讓汪何修線路使各個站點都能聯通， 同時修的線路里程最短？
10. 最小生成樹 普里姆演算法和克魯斯卡爾演算法
kruskal演算法的時間復雜度主要由排序方法決定，其排序演算法只與帶權邊的個數有關，與圖中頂點的個數無關，當使用時間復雜度為O（eloge）的排序演算法時，克魯斯卡演算法的時間復雜度即為O（eloge），因此當帶權圖的頂點個數較多而邊的條數較少時，使用克魯斯卡爾演算法構造最小生成樹效果最好！
克魯斯卡爾演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾演算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。
普里姆演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。
--以上傳自http://hi..com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html
1.Kruskal
//題目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1258
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定義邊集
int cmp(const void *a,const void *b)//快排比較函數
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v為點集
void makeset(int n)
{
for(int i=0;i<n;i++)
v[i]=i;
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i<p;i++)
{
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}
2.Prim
//題目地址同上
#include <iostream>
using namespace std;
#define M 101
#define maxnum 100001
int dis[M][M];
int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i] = dis[1][i];
used[1] = true;
int sum=0;
for(i=1; i<n; i++){
int temp=maxnum;
for(j=1; j<=n; j++){
if( !used[j] && d[j]<temp ){
temp = d[j];
k = j;
}
}
used[k] = true;
sum += d[k];
for(j=1; j<=n; j++){
if( !used[j] && dis[k][j]<d[j] )
d[j] = dis[k][j]; // 與Dijksta演算法的差別之處
}
}
return sum;
}
int main()
{
int n,i,j;
while( cin>>n ){
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if( !dis[i][j] )
dis[i][j] = maxnum;
}
}
cout<<prim(n)<<endl;
}
return 0;
}
代碼來自網路