数学建模最小生成树kruskal算法及各种代码.docx
《数学建模最小生成树kruskal算法及各种代码.docx》由会员分享，可在线阅读，更多相关《数学建模最小生成树kruskal算法及各种代码.docx（24页珍藏版）》请在冰点文库上搜索。
数学建模最小生成树kruskal算法及各种代码
kruskal算法及代码
---含伪代码、c代码、matlab、pascal等代码
Kruskal算法每次选择n-1条边，所使用的贪婪准则是：
从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。
注意到所选取的边若产生环路则不可能形成一棵生成树。
Kruskal算法分e步，其中e是网络中边的数目。
按耗费递增的顺序来考虑这e条边，每次考虑一条边。
当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
Kruskal算法
1.算法定义
2.举例描述
Kruskal算法的代码实现
1.伪代码
2.C代码实现
3.matlab代码实现
4.pascal代码实现
Kruskal算法
1.算法定义
2.举例描述
Kruskal算法的代码实现
1.伪代码
2.C代码实现
3.matlab代码实现
4.pascal代码实现
算法定义
克鲁斯卡尔算法
假设WN=（V,{E}）是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：
先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。
之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。
依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。
举例描述
克鲁斯卡尔算法（Kruskal'salgorithm）是两个经典的最小生成树算法的较为简单理解的一个。
这里面充分体现了贪心算法的精髓。
大致的流程可以用一个图来表示。
这里的图的选择借用了Wikipedia上的那个。
非常清晰且直观。
首先第一步，我们有一张图，有若干点和边
如下图所示：
第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。
这里再次体现了贪心算法的思想。
资源排序，对局部最优的资源进行选择。
排序完成后，我们率先选择了边AD。
这样我们的图就变成了
第二步，在剩下的变中寻找。
我们找到了CE。
这里边的权重也是5
依次类推我们找到了6,7,7。
完成之后，图变成了这个样子。
.
下一步就是关键了。
下面选择那条边呢BC或者EF吗都不是，尽管现在长度为8的边是最小的未选择的边。
但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。
所以我们不需要选择他们。
类似的BD也已经连通了（这里上图的连通线用红色表示了）。
最后就剩下EG和FG了。
当然我们选择了EG。
最后成功的图就是下图：
.
到这里所有的边点都已经连通了，一个最小生成树构建完成。
编辑本段Kruskal算法的代码实现
伪代码
MST-KRUSKAL（G，w）
C代码实现
/*
Copyright（c）2002,2006byctu_85
AllRightsReserved.
*/
/*Iamsorrytosaythatthesituationofunconnectedgraphisnotconcerned*/
#include""
#definemaxver10
#definemaxright100
intG[maxver][maxver],record=0,touched[maxver][maxver];
intcircle=0;
intFindCircle（int,int,int,int）;
intmain（）
{
intpath[maxver][2],used[maxver][maxver];
inti,j,k,t,min=maxright,exsit=0;
intv1,v2,num,temp,status=0;
restart:
printf（"Pleaseenterthenumberofvertex（s）inthegraph:
\n"）;
scanf（"%d",&num）;
if（num>maxver||num<0）
{
printf（"Error!
Pleasereinput!
\n"）;
gotorestart;
}
for（j=0;j for（k=0;k {
if（j==k）
{
G[j][k]=maxright;
used[j][k]=1;
touched[j][k]=0;
}
else
if（j {
re:
printf（"Pleaseinputtherightbetweenvertex%dandvertex%d,ifnoedgeexistspleaseinput-1:
\n",j+1,k+1）;
scanf（"%d",&temp）;
if（temp>=maxright||temp<-1）
{
printf（"Invalidinput!
\n"）;
gotore;
}
if（temp==-1）
temp=maxright;
G[j][k]=G[k][j]=temp;
used[j][k]=used[k][j]=0;
touched[j][k]=touched[k][j]=0;
}
}
for（j=0;j {
path[j][0]=0;
path[j][1]=0;
}
for（j=0;j {
status=0;
for（k=0;k if（G[j][k] {
status=1;
break;
}
if（status==0）
break;
}
for（i=0;i {
for（j=0;j for（k=0;k if（G[j][k]used[j][k]）
{
v1=j;
v2=k;
min=G[j][k];
}
if（!
used[v1][v2]）
{
used[v1][v2]=1;
used[v2][v1]=1;
touched[v1][v2]=1;
touched[v2][v1]=1;
path[0]=v1;
path[1]=v2;
for（t=0;t FindCircle（path[t][0],path[t][0],num,path[t][0]）;
if（circle）
{/*ifacircleexsits,rollback*/
circle=0;
i--;
exsit=0;
touched[v1][v2]=0;
touched[v2][v1]=0;
min=maxright;
}
else
{
record++;
min=maxright;
}
}
}
if（!
status）
printf（"Wecannotdealwithitbecausethegraphisnotconnected!
\n"）;
else
{
for（i=0;i printf（"Path%d:
vertex%dtovertex%d\n",i+1,path[0]+1,path[1]+1）;
}
return1;
}
intFindCircle（intstart,intbegin,inttimes,intpre）
{/*tojudgewhetheracircleisproduced*/
inti;
for（i=0;i if（touched[begin]==1）
{
if（i==start&&pre!
=start）
{
circle=1;
return1;
break;
}
else
if（pre!
=i）
FindCircle（start,i,times,begin）;
else
continue;
}
return1;
}
matlab代码实现
functionKruskal（w,MAX）
%此程序为最小支撑树的Kruskal算法实现
%w为无向图的距离矩阵，故为对称矩阵
%MAX为距离矩阵中∞的实际输入值
%时间：
2011年6月22日0:
07:
53
len=length（w）;%图的点数
edge=zeros（len*（len-1）,3）;%用于存储图中的边
count=1;%图中的边数
fori=1:
len-1%循环距离矩阵，记录存储边
forj=i+1:
len
ifw（i,j）~=MAX
edge（count,1）=w（i,j）;
edge（count,2）=i;
edge（count,3）=j;
count=count+1;
end
end
end
edge=edge（1:
count-1,:
）;%去掉无用边
[tmp,index]=sort（edge（:
1））;%所有边按升序排序
i=3;%其实测试边数为3条（3条以下无法构成圈，即无需检测）
while1
x=findcycle（edge（index（1:
i）,:
）,len）;%检测这些边是否构成圈
ifx
index（i）=0;%若构成圈，则将该边对应的index项标记为0，以便除去
else
i=i+1;%若没有构成圈，则i加1，加入下一边检测
end
index=index（index>0）;%将构成圈的边从index中除去
ifi==len
break;%找到符合条件的点数减一条的边，即找到一个最小支撑树
end
end
index=index（1:
len-1）;%截短index矩阵，保留前len-1项
%%%%%%%%%%%%结果显示%%%%%%%%%%%%%
s=sprintf（'\n\t%s\t%s\t%s\t','边端点','距离','是否在最小支撑树'）;
fori=1:
count-1
edge_tmp=edge（i,:
）;
if~isempty（find（index==i,1））
s_tmp=sprintf（'\n\t（%d,%d）\t%d\t%s\t',edge_tmp
（2）,edge_tmp（3）,edge_tmp
（1）,'√'）;
else
s_tmp=sprintf（'\n\t（%d,%d）\t%d\t%s\t',edge_tmp
（2）,edge_tmp（3）,edge_tmp
（1）,'×'）;
end
s=strcat（s,s_tmp）;
end
disp（s）;
end
functionisfind=findcycle（w,N）
%本程序用于判断所给的边能否构成圈：
有圈，返回1；否则返回0
%w：
输入的边的矩阵
%N：
原图的点数
%原理：
不断除去出现次数小于2的端点所在的边，最后观察是否有边留下
len=length（w（:
1））;
index=1:
len;
while1
num=length（index）;%边数
p=zeros（1,N）;%用于存储各点的出现的次数（一条边对应两个端点）
fori=1:
num%统计各点的出现次数
p（w（index（i）,2））=p（w（index（i）,2））+1;
p（w（index（i）,3））=p（w（index（i）,3））+1;
end
index_tmp=zeros（1,num）;%记录除去出现次数小于2的端点所在的边的边的下标集合
discard=find（p<2）;%找到出现次数小于2的端点
count=0;%记录剩余的边数
fori=1:
num
%判断各边是否有仅出现一次端点——没有，则记录其序号于index_tmp
if~（~isempty（find（discard==w（index（i）,2）,1））||~isempty（find（discard==w（index（i）,3）,1）））
count=count+1;
index_tmp（count）=index（i）;
end
end
ifnum==count%当没有边被被除去时，循环停止
index=index_tmp（1:
count）;%更新index
break;
else
index=index_tmp（1:
count）;%更新index
end
end
ifisempty（index）%若最后剩下的边数为0，则无圈
isfind=0;
else
isfind=1;
end
end
%
%a=[
%0323100100100
%3021001001006
%22031001100
%3100305100100
%1001001005046
%1001001100405
%1006100610050];
%
%Kruskal（a,100）
pascal代码实现
{
最小生成树的Kruskal算法。
Kruskal算法基本思想：
每次选不属于同一连通分量（保证不生成圈）且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量
排序使用Quicksort（O（eloge））
检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数
Union-Find使用rank启发式合并和路径压缩
总复杂度O（eloge）=O（elogv）（因为e }
const
maxn=100;
maxe=maxn*maxn;
type
edge=record
a,b:
integer;maxe]ofedge;maxn]ofinteger;en;
i:
=l;j:
=r;
repeat
whileedges[i].len whileedges[j].len>xdodec（j）;
ifi<=jthen
begin
swap（i,j）;
inc（i）;dec（j）;
end
untili>j;
ifl ifi end;
procedureinit;
var
i:
integer;
begin
assign（input,''）;reset（input）;
readln（n,e）;
fori:
=1toedoreadln（edges[i].a,edges[i].b,edges[i].len）;
例题详见vijosp1045Kerry的电缆网络
type
rec=record
x,y:
longint;
cost:
real;
end;
var
f:
array[1..1000000]ofrec;
s,ans:
real;
i,n,m,k,dad:
longint;
father:
array[1..1000000]oflongint;
procedurekp（l,r:
longint）;
var
i,j:
longint;
xx:
real;
y:
rec;
begin
i:
=l;
j:
=r;
xx:
=f[（i+j）div2].cost;
repeat
whilexx>f[i].costdoinc（i）;
whilexx ifi<=jthen
begin
y:
=f[i];
f[i]:
=f[j];
f[j]:
=y;
inc（i）;
dec（j）;
end;
untili>j;
ifi ifl end;
functionfind（x:
longint）:
longint;
begin
iffather[x]=xthenexit（x）;
father[x]:
=find（father[x]）;
exit（father[x]）;
end;
procedureunion（x,y:
longint;j:
real）;
begin
x:
=find（x）;
y:
=find（y）;
ifx<>ythen
begin
father[y]:
=x;
ans:
=ans+j;
inc（k）;
end;
end;
begin
readln（s）;
readln（n）;
m:
=0;
whilenoteofdo
begin
inc（m）;
withf[m]do
readln（x,y,cost）;
end;
ifm begin
writeln（'Impossible'）;
exit;
end;
fori:
=1tondo
father[i]:
=i;
kp（1,m）;
k:
=0;
fori:
=1tomdo
begin
ifk=n-1thenbreak;
union（f[i].x,f[i].y,f[i].cost）;
end;
ifk begin
writeln（'Impossible'）;
exit;
end;
ifans>sthenwriteln（'Impossible'）else
writeln（'Need',ans:
0:
2,'milesofcable'）;
end.
Kruskal算法适用于边稀疏的情形，而Prim算法适用于边稠密的情形
其它最小生成树算法
c++代码实现
#include<>
#include<>
#include
usingnamespacestd;
#defineMAXNUM_VERTEX20=a;
[j].w=c;
[j].weight=d;
}
else
gotop1;
}
}
voidsort_by_weight（）
{
for（inti=1;i<;i++）
{
Edgetemp=[i];
for（intj=i-1;j>=0&&[j].weight>;j--）
[j+1]=[j];
[j+1]=temp;
}
}
/*不相交集处理函数*/
inlinevoidmakeset（vector&array）
{
for（inti=0;i<（）;i++）
array[i]=i;
}
intfindset（vector&parent,inti）
{
if（i!
=parent[i]）
i=parent[i];
returni;
}
inlinevoidmerge（vector&parent,inti,intj）
{
parent[i]=j;
}
/*不相交集处理函数*/
voidkruskal（）
{
intnum_ver=;
intcount=0;
vectorparent_ver;
（num_ver）;
/*核心部分是用不相交集合成树*/
makeset（parent_ver）;
printf（"theedgeofmintreeasfollow:
\n"）;
for（inti=0;i intn=[i].w;
intw=[i].weight;
if（findset（parent_ver,m）!
=findset（parent_ver,n））,[i].w,[i].weight）;
}
voidmain（）
{
create_graph（）;
sort_by_weight（）;
print_edge（）;
升级会员 