最小生成樹其實是最小權重生成樹的簡稱。一個有n個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有n個結點，并且有保持圖連通的最少的邊。最小生成樹可以用kruskal（克魯斯卡爾）算法或Prim（普里姆）算法求出。最小生成樹性質：設G=(V，E）是一個連通網絡，U是頂點集V的一個非空真子集。根據樹的定義，則T中必有一條從紅點u到藍點v的路徑P，且P上必有一條紫邊（u'，v'）連接紅點集和藍點集，否則u和v不連通。當一條邊（u，v）加入T時，必須保證T∪(u，v)仍是MST的子集，我們將這樣的邊稱為T的安全邊。
應用
生成樹和最小生成樹有許多重要的應用。
例如：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。
性質
說明
最小生成樹性質：設是一個連通網絡，U是頂點集V的一個非空真子集。若(u，v）是G中一條“一個端點在U中（例如：），另一個端點不在U中的邊（例如：），且（u，v）具有最小權值，則一定存在G的一棵最小生成樹包括此邊（u，v）。
證明
為方便說明，先作以下約定：
①將集合U中的頂點看作是紅色頂點，②而V-U中的頂點看作是藍色頂點，③連接紅點和藍點的邊看作是紫色邊，④權最小的紫邊稱為輕邊（即權重最"輕"的邊）。于是，MST性質中所述的邊（u，v）就可簡稱為輕邊。
用反證法證明MST性質：
假設G中任何一棵MST都不含輕邊（u，v）。則若T為G的任意一棵MST，那么它不含此輕邊。
根據樹的定義，則T中必有一條從紅點u到藍點v的路徑P，且P上必有一條紫邊（u'，v'）連接紅點集和藍點集，否則u和v不連通。當把輕邊（u，v）加入樹T時，該輕邊和P必構成了一個回路。刪去紫邊（u'，v'）后回路亦消除，由此可得另一生成樹T'。
T'和T的差別僅在于T'用輕邊（u，v）取代了T中權重可能更大的紫邊（u'，v'）。因為，所以
即T'是一棵比T更優的MST，所以T不是G的MST，這與假設矛盾。
所以，MST性質成立。
算法描述
求MST的一般算法可描述為：針對圖G，從空樹T開始，往集合T中逐條選擇并加入條安全邊（u，v），最終生成一棵含條邊的MST。
當一條邊（u，v）加入T時，必須保證仍是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，…，來表示頂點集，即是：
，
G中邊上的權解釋為長度，并設。
求最小生成樹的具體算法（pascal):
Prim算法
procedure 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]<>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]:=cost[k,j];
closest[j]:=k;
end;
end;
end;
Kruskal算法
按權值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。
函數 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;
procedure 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語言代碼
kruskal
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;
procedure 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 xdec(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
if l
end;
函數 find(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=find(fa[x]);
find:=fa[x];
end;
procedure 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)
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:=;
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]
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.
參考資料 >