最小生成树

最小生成树其实是最小权重生成树的简称。一个有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):

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;

按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。

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;

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186#include<stdio.h>#include<stdlib.h>#include<iostream.h>#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineMAX1000typedefstructArcell{double adj ;}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;//节点1char ch2 ;//节点2double value ;//权值}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 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;double temp ;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);}

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;

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)

begin

union(s,t);

ans:=ans+len;

inc(count);

end;

end;

write(ans);

end.

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.