更新时间：2024-04-03 16:21
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得联通所有结点的的 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。
生成树和最小生成树有许多重要的应用。
例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
说明
最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。若(u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边（例如：v∈V-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括此边（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'）。因为w(u，v）≤w（u'，v'），所以
w(T')=w(T)+w(u，v)-w(u'，v'）≤w(T)
即T'是一棵比T更优的MST，所以T不是G的MST，这与假设矛盾。
所以，MST性质成立。
求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。
当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。
Prim算法简述
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew= {},为空；
3).重复下列操作，直到Vnew= V：
a.在集合E中选取权值最小的边
b.将v加入集合Vnew中，将
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
Kruskal算法简述
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
伪代码
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）。
C语言代码
Kruskal算法 - 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;
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 x if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i);dec(j); end; until i>j; if i if l end; function find(x:longint):longint; begin if fa[x]=x then exit(x); fa[x]:=find(fa[x]);{路径压缩} exit(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)<>find(t) then begin union(s,t); ans:=ans+len; inc(count); end; end; write(ans); end. Prim算法 - pascal语言 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] 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. C++模板