一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。

概述

应用

性质（MST性质）(（1）MST性质 （2）MST性质的证明)

MST的一般算法描述

Kruskal算法

概述

在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。

许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

应用

生成树和最小生成树有许多重要的应用。

【例】网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价）。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

性质（MST性质）

（1）MST性质

最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个真子集。若(u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边（例如：v∈V-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括此边（u，v）。

（2）MST性质的证明

为方便说明，先作以下约定：

①将集合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'）。因为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的一般算法描述

求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):

A.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:=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;

B.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;

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语言完整代码如下（已编译通过）：

#include<stdio.h>

#include<stdlib.h>

#include<iostream.h>

#define MAX_VERTEX_NUM 20

#define OK 1

#define ERROR 0

#define MAX 1000

typedef struct Arcell

{

double adj;

}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

char vexs[MAX_VERTEX_NUM]; //节点数组

AdjMatrix arcs; //邻接矩阵

int vexnum,arcnum; //图的当前节点数和弧数

}MGraph;

typedef struct Pnode //用于普利姆算法

{

char adjvex; //节点

double lowcost; //权值

}Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集U到V-U的代价最小的边的辅助数组定义

typedef struct Knode //用于克鲁斯卡尔算法中存储一条边及其对应的2个节点

{

char ch1; //节点1

char ch2; //节点2

double value;//权值

}Knode,Dgevalue[MAX_VERTEX_NUM];

//-----------------------------------------------------------------------------------

int CreateUDG(MGraph & G,Dgevalue & dgevalue);

int LocateVex(MGraph G,char ch);

int Minimum(MGraph G,Closedge closedge);

void MiniSpanTree_PRIM(MGraph G,char u);

void Sortdge(Dgevalue & dgevalue,MGraph G);

//-----------------------------------------------------------------------------------

int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵

{

int i,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;

}

return OK;

}

int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置

{

int a ;

for(int i=0; i<G.vexnum; i++)

{

if(G.vexs[i] == ch)

a=i;

}

return a;

}

void MiniSpanTree_PRIM(MGraph G,char u)//普利姆算法求最小生成树

{

int i,j,k;

Closedge closedge;

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;

}

}

}

}

int Minimum(MGraph G,Closedge closedge) //求closedge中权值最小的边，并返回其顶点在vexs中的位置

{

int i,j;

double k = 1000;

for(i=0; i<G.vexnum; i++)

{

if(closedge[i].lowcost != 0 && closedge[i].lowcost < k)

{

k = closedge[i].lowcost;

j = i;

}

}

return j;

}

void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)//克鲁斯卡尔算法求最小生成树

{

int p1,p2,i,j;

int bj[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;

}

}

}

}

void Sortdge(Dgevalue & dgevalue,MGraph G)//对dgevalue中各元素按权值按从小到大排序

{

int i,j;

double temp;

char ch1,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;

}

}

}

}

void main()

{

int i,j;

MGraph G;

char u;

Dgevalue dgevalue;

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<<"=============普利姆算法===============\";

cout<<"请输入起始点：";

cin>>u;

cout<<"构成最小代价生成树的边集为：\";

MiniSpanTree_PRIM(G,u);

cout<<"============克鲁斯科尔算法=============\";

cout<<"构成最小代价生成树的边集为：\";

MiniSpanTree_KRSL(G,dgevalue);

}

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 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;

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.