㈠ 最小生成樹的定義以及有關演算法
Kruskal演算法和Prim演算法
任何只由G的邊構成,並包含G的所有頂點的樹稱為G的生成樹(G連通).
加權無向圖G的生成樹的代價是該生成樹的所有邊的代碼(權)的和.
最小代價生成樹是其所有生成樹中代價最小的生成樹.
參考代碼:
(僅為主程序,更多代碼在
http://www.supcoder.cn/bbs/dispbbs.asp?boardID=1&ID=69&page=1
解壓密碼:www.supcoder.cn )
#include "Sets.h"
#include "themap.h"
#include "windows.h"
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/*
功能:
演示Kruskal演算法和Prim演算法
集合的並,元素查找的操作及應用
說明:
代碼均在vc++6.0環境下編譯均通過
在非VC++6.0環境下編譯請去掉頭文件 windows.h 和函數 end()
如果NULL未定義請自定義
#define NULL 0 或
#define NULL ((void*)0)
作者:
hacker
時間:
2007.2.3
*/
const VSIZE = 7;//7個頂點
const INFINITY = 10000;//10000作為無窮大來處理
void LoadData(int cost[][VSIZE+1], Edge edge[]);
void end();
/*
函數名:
Kruskal 和 Prim
參數:
邊,代價,邊數,頂點數,最小代價生成樹的頂點
返回值:
返回值為-1,不存在最小代價生成樹
返回值大於0時為最小代價生成樹的代價
最小代價生成樹的邊在vector<Edge>& t
*/
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int Prim (Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int main()
{
int cost[VSIZE+1][VSIZE+1];//0不用
Edge edge[9];//9條邊
vector<Edge> t;//用來存儲最小代價生成樹的頂點
int mincost;//最小代價
LoadData(cost, edge);
if ( (mincost = Kruskal(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代價是:"<<mincost<<endl<<"邊是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}
t.clear();
if ( (mincost = Prim(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代價是:"<<mincost<<endl<<"邊是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}
end();
return 1;
}
void LoadData(int cost[][VSIZE+1], Edge edge[])
{
edge[0].u = 1; edge[0].v = 2; edge[0].weight = 28;
edge[1].u = 1; edge[1].v = 6; edge[1].weight = 10;
edge[2].u = 2; edge[2].v = 3; edge[2].weight = 16;
edge[3].u = 2; edge[3].v = 7; edge[3].weight = 14;
edge[4].u = 3; edge[4].v = 4; edge[4].weight = 12;
edge[5].u = 4; edge[5].v = 5; edge[5].weight = 22;
edge[6].u = 4; edge[6].v = 7; edge[6].weight = 18;
edge[7].u = 5; edge[7].v = 6; edge[7].weight = 25;
edge[8].u = 5; edge[8].v = 7; edge[8].weight = 24;
for (int i=1;i<=7;i++)
for (int j=1;j<=i;j++)
cost[i][j] = cost[j][i] = INFINITY;
for (i=0;i<9;i++)
cost[edge[i].u][edge[i].v] =
cost[edge[i].v][edge[i].u] = edge[i].weight;
}
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
Sets s(esize);
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
int mincost = 0;
for (int i = 0;i<esize;i++)
//把所有的邊放入優先隊列
pq.push(edge[i]);
i = 0;
while (i<vsize-1 && !pq.empty())
{
Edge temp = pq.top();//取出當前權最小的邊
pq.pop();
int j = s.SimpleFind(temp.u);
int k = s.SimpleFind(temp.v);
if (j!=k)//如果不構成環
{
i++;
t.push_back(temp);
mincost +=cost[temp.u][temp.v];
s.SimpleUnion(j, k);
}
}
if (i!=vsize-1)
{
t.clear();
return -1;
}
else
{
return mincost;
}
}
int Prim(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
vector<Edge> sortededge;
int i;
for (i =0;i<esize;i++)
pq.push(edge[i]);
for (i =0;i<esize;i++)
{//對邊進行從小到大排列,放到sortededge中
sortededge.push_back(pq.top());
pq.pop();
}
int distance[VSIZE+1];
int j;
int mincost = sortededge[0].weight;
Edge temp = sortededge[0];
t.push_back(temp);
for (i=1;i<=vsize;i++)
distance[i] = 1;//每個點都不在已生成樹里
distance[temp.u] = distance[temp.v] = 0;//最短的邊的兩個點放到生成樹里
for (i=2;i<=vsize-1;i++)
{//尋找另外的邊
int exist = 0;//設置是否找到符合條件的邊的狀態標志為未找到
for (j=1;j<esize;j++)
if (distance[sortededge[j].u] ^ distance[sortededge[j].v] == 1)
{//由於邊是排序好了的,所以從小邊向大邊找,找到的第一個符合條件的邊可以
//加到生成樹里
int k = (distance[sortededge[j].u] == 0) ? sortededge[j].v :\
sortededge[j].u;
distance[k] = 0;
mincost += sortededge[j].weight;
t.push_back(sortededge[j]);
exist = 1;
break;
}
if (!exist)
{
t.clear();
return -1;
}
}
return mincost;
}
void end()
{
if (MessageBox(NULL,\
"歡迎到http://www.supcoder.cn學習交流(源代碼在論壇下載)\n\t\t(確定後自動訪問論壇)",\
"supcoder", IDOK) == IDOK)
{
char cmdLine[] = "iexplore http://www.supcoder.cn/bbs";
char path[256];
char buf[256];
STARTUPINFO si;
ZeroMemory(&si, sizeof(si));
PROCESS_INFORMATION ProcessInformation;
GetSystemDirectory(buf, 256);
sprintf(path, "%c:\\Program Files\\Internet Explorer\\IEXPLORE.EXE", buf[0]);
CreateProcess(path,cmdLine, NULL, NULL, 1, 0, NULL, NULL, &si, &ProcessInformation);
}
cout<<"==============================================================================="<<endl;
cout<<"\t\t\t\t 謝謝使用!"<<endl;
cout<<"\t\t\t http://www.supcoder.cn"<<endl;
Sleep(1000);
}
㈡ 數據結構（十）：最小生成樹
最小生成樹是帶權無向連通圖中權值最小的生成樹，根據 圖 中生成樹定義可知， 個頂點的連通圖中，生成樹中邊的個數為 ，向生成樹中添加任意一條邊，則會形成環。生成樹存在多種，其中權值之和最小的生成樹即為最小生成樹。
若 為最小生成樹 的一個真子集，即 的頂點集合和邊集合都是 的頂點和邊集合的子集，構造最小生成樹過程為向 中添加頂點和邊，添加的原則有兩種：
kruskal 演算法即為上述第一種原則，通過選擇圖中的最小權值邊來構造最小生成樹，過程中需要注意避免形成環。
step 1：
最小權值邊為頂點 7、8 形成的邊
step 2：
最小權值邊為頂點 3、9 形成的邊
step 3：
最小權值邊為頂點 6、7 形成的邊
step 4：
最小權值邊為頂點 3、6 形成的邊
step 5：
最小權值邊為頂點 1、2 形成的邊
step 6：
最小權值邊為頂點 3、4 形成的邊
step 7：
最小權值邊為頂點 1、8 形成的邊
step 8：
最小權值邊為頂點 4、5 形成的邊
最小生成樹的權值之和為 37
這里使用鄰接表作為圖的存儲結構
這里使用 getEdgesFromAdjacencyList 函數完成鄰接表到邊集合的轉換，使用快排 sort 完成對邊集合的排序，使用 origin 函數返回每個子圖的根。
該函數返回頂點 index 所屬子圖的根頂點，其中 vertices[index] 位置上存儲的是頂點 index 的上一個頂點，每個子圖中，根頂點的上一個頂點為自身。
kruskal 演算法中使用 getEdgesFromAdjacencyList 函數完成鄰接表向邊集合的轉換，函數內部存在兩層循環，訪問鄰接表中每個頂點的相鄰頂點，復雜度為 。使用快排對邊集合進行排序，時間復雜度為 ，因為 ，所以快排時間復雜度可以表述為 。 kruskal 演算法中 while 循環取最小權值邊，並對邊的兩個頂點執行 origin 函數判斷是否屬於同一個子圖，時間復雜度為 。所以 kruskal 演算法的時間復雜度為 。
kruskal 演算法的過程為不斷對子圖進行合並，直到形成最終的最小生成樹。 prim 演算法的過程則是只存在一個子圖，不斷選擇頂點加入到該子圖中，即通過對子圖進行擴張，直到形成最終的最小生成樹。
step 1：
距離子圖的最近頂點為 4
step 2：
距離子圖的最近頂點為 3
step 3：
距離子圖的最近頂點為 9
step 4：
距離子圖的最近頂點為 6
step 5：
距離子圖的最近頂點為 7
step 6：
距離子圖的最近頂點為 8
step 7：
距離子圖的最近頂點為 2
step 8：
距離子圖的最近頂點為 1
最小生成樹的權值之和為 37
這里使用鄰接表作為圖的存儲結構
這里使用 vertices 列表存儲每個頂點元素，每個元素包括兩個屬性， index 為頂點下標， weight 為頂點距離子圖的大小。演算法中使用 verticesIndex 列表存儲每個頂點元素在 vertices 列表中的下標位置。使用 heapSort 堆排序對每個頂點到子圖的距離進行排序，即對 vertices 列表進行排序，使用堆排序內的 transformToHeap 函數調整 vertices 列表為小頂堆。當添加新頂點到子圖後，使用 updateVertices 函數完成對相鄰頂點的距離更新。
當 vertices 列表調整為小頂堆之後，將列表首、尾元素交換，則列表尾元素即為距離子圖最近的頂點元素。
對每一個相鄰頂點，如果不在子圖中，則判斷是否更新到子圖的距離。更新距離後的 while 循環操作，目的為調整堆結構為小頂堆。
prim 演算法中構造頂點列表的時間復雜度為 。使用堆排序對頂點列表進行排序，時間復雜度為 。 prim 演算法中 while 循環取最近頂點元素，並調整元素取出後列表的堆結構，所以調整復雜度為 ；同時，循環結構內執行 updateVertices 函數，更新每個取出頂點的相鄰頂點距離值，所以更新頂點數為 ，因為每個頂點更新距離後，需要調整堆結構為小頂堆，所以更新復雜度為 。所以 prim 演算法的總時間復雜度為 。
㈢ 最小生成樹怎麼求
一個有 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.
㈣ 最小生成樹的兩種演算法
主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。
㈤ 最小生成樹的兩種演算法
主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。
㈥ 圖的最小生成樹演算法
圖的生成樹和最小生成樹生成樹(SpanningTree):如果一個圖的子圖是一個包含圖所有節點的樹,那這個子圖就稱為生成樹.
㈦ 最小生成樹
最小生成樹演算法.可以用PRIM演算法....你簡單看看
普里姆(Prim)演算法
（1）演算法思想 通過每次添加一個新節點加入集合，直到所有點加入停止的最小生成樹的演算法
原理：每次連出該集合到其他所有點的最短邊保證生成樹的邊權總和最小
1. 首先隨便選一個點加入集合
2. 用該點的所有邊去刷新到其他點的最短路
3. 找出最短路中最短的一條連接（且該點未被加入集合）
4. 用該點去刷新到其他點的最短路
5 重復以上操作n-1次
6 最小生成樹的代價就是連接的所有邊的權值之和
void MiniSpanTree_P( MGraph G, VertexType u )
{
//用普里姆演算法從頂點u出發構造網G的最小生成樹
k = LocateVex ( G, u );
for ( j=0; j<G.vexnum; ++j ) // 輔助數組初始化
if (j!=k)
closedge[j] = { u, G.arcs[k][j] };
closedge[k].Lowcost = 0; // 初始，U＝{u}
for ( i=0; i<G.vexnum; ++i )
{
繼續向生成樹上添加頂點；
}
k = minimum(closedge); // 求出加入生成樹的下一個頂點(k)
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] < closedge[j].Lowcost )
closedge[j] = { G.vexs[k], G.arcs[k][j] };
}
㈧ 圖的相關演算法（二）：最小生成樹演算法
在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，並使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。
例如，對於上圖中的連通網可以有多棵權值總和不相同的生成樹。
克魯斯卡爾（Kruskal）演算法，是用來求加權連通圖的最小生成樹的演算法。
基本思想 ：按照權值從小到大的順序選擇n-1條邊，並保證這n-1條邊不構成迴路。
具體做法 ：首先構造一個只含n個頂點的森林，然後依照權值從小到大從連通網中選擇邊加入到森林中，並使得森林不產生迴路，直到森林變成一棵樹為止。
以圖G4為例（更詳細的可以參考《演算法導論》p367），對Kruskal進行演示（假設，用數組R保存最小生成樹結果）。
第1步 ：將邊<E,F>加入R中。
邊<E,F>的權值最小，因此將它加入到最小生成樹結果R中。
第2步 ：將邊<C,D>加入R中。
上一步操作之後，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中。
第3步 ：將邊<D,E>加入R中。
上一步操作之後，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中。
第4步 ：將邊<B,F>加入R中。
上一步操作之後，邊<C,E>的權值最小，但<C,E>會和已有的邊構成迴路；因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結果R中。
第5步 ：將邊<E,G>加入R中。
上一步操作之後，邊<E,G>的權值最小，因此將它加入到最小生成樹結果R中。
第6步 ：將邊<A,B>加入R中。
上一步操作之後，邊<F,G>的權值最小，但<F,G>會和已有的邊構成迴路；因此，跳過邊<F,G>。同理，跳過邊<B,C>。將邊<A,B>加入到最小生成樹結果R中。
此時，最小生成樹構造完成！它包括的邊依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。
根據前面介紹的克魯斯卡爾演算法的基本思想和做法，我們能夠了解到，克魯斯卡爾演算法重點需要解決的以下兩個問題：
問題一 對圖的所有邊按照權值大小進行排序。
問題二 將邊添加到最小生成樹中時，怎麼樣判斷是否形成了迴路。
問題一用排序演算法排序即可。
問題二，處理方式：記錄頂點在「最小生成樹」中的終點，頂點的終點是「在最小生成樹中與它連通的最大頂點"(關於這一點，後面會通過圖片給出說明)。然後每次需要將一條邊添加到最小生成樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成迴路。 以下圖來進行說明：
在將<E,F> <C,D> <D,E>加入到最小生成樹R中之後，這幾條邊的頂點就都有了終點：
關於終點，就是將所有頂點按照從小到大的順序排列好之後；某個頂點的終點就是"與它連通的最大頂點"。 因此，接下來，雖然<C,E>是權值最小的邊。但是C和E的重點都是F，即它們的終點相同，因此，將<C,E>加入最小生成樹的話，會形成迴路。這就是判斷迴路的方式。
普里姆（Prim）演算法，也是求加權連通圖的最小生成樹的演算法。
基本思想
對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。從所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有頂點）的邊中選取權值最小的邊（u，v），將頂點v加入U中，將邊（u,v）加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，此時集合T中包含了最小生成樹中的所有邊。
以上圖G4為例，來對普里姆進行演示(從第一個頂點A開始通過普里姆演算法生成最小生成樹)。
初始狀態 ：V是所有頂點的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：將頂點A加入到U中。
此時，U={A}。
第2步 ：將頂點B加入到U中。
上一步操作之後，U={A}, V-U={B,C,D,E,F,G}；因此，邊(A,B)的權值最小。將頂點B添加到U中；此時，U={A,B}。
第3步 ：將頂點F加入到U中。
上一步操作之後，U={A,B}, V-U={C,D,E,F,G}；因此，邊(B,F)的權值最小。將頂點F添加到U中；此時，U={A,B,F}。
第4步 ：將頂點E加入到U中。
上一步操作之後，U={A,B,F}, V-U={C,D,E,G}；因此，邊(F,E)的權值最小。將頂點E添加到U中；此時，U={A,B,F,E}。
第5步 ：將頂點D加入到U中。
上一步操作之後，U={A,B,F,E}, V-U={C,D,G}；因此，邊(E,D)的權值最小。將頂點D添加到U中；此時，U={A,B,F,E,D}。
第6步 ：將頂點C加入到U中。
上一步操作之後，U={A,B,F,E,D}, V-U={C,G}；因此，邊(D,C)的權值最小。將頂點C添加到U中；此時，U={A,B,F,E,D,C}。
第7步 ：將頂點G加入到U中。
上一步操作之後，U={A,B,F,E,D,C}, V-U={G}；因此，邊(F,G)的權值最小。將頂點G添加到U中；此時，U=V。
此時，最小生成樹構造完成！它包括的頂點依次是：A B F E D C G。