数学建模-小生成树-kruskal算法及各种代码

数学建模-最小生成树-kruskal算法及各种代码数学建模-最小生成树-kruskal算法及各种代码数学建模-最小生成树-kruskal算法及各种代码资料仅供参考文件编号：2022年4月数学建模-小生成树-kruskal算法及各种代码版本号：A修改号：1页次：1.0审核：批准:发布日期：kruskal算法及代码---含伪代码、c代码、matlab、pascal等代码Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。目录Kruskal算法Kruskal算法的代码实现Kruskal算法Kruskal算法的代码实现算法定义克鲁斯卡尔算法假设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_85AllRightsReserved.*//*Iamsorrytosaythatthesituationofunconnectedgraphisnotconcerned*/#include""#definemaxver10#definemaxright100intG[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<num;j++)for(k=0;k<num;k++){if(j==k){G[j][k]=maxright;used[j][k]=1;touched[j][k]=0;}elseif(j<k){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<num;j++){path[j][0]=0;path[j][1]=0;}for(j=0;j<num;j++){status=0;for(k=0;k<num;k++)if(G[j][k]<maxright){status=1;break;}if(status==0)break;}for(i=0;i<num-1&&status;i++){for(j=0;j<num;j++)for(k=0;k<num;k++)if(G[j][k]<min&&!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<record;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<num-1;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<times;i++)if(touched[begin]==1）{if(i==start&&pre!=start){circle=1;return1;break;}elseif(pre!=i)FindCircle(start,i,times,begin);elsecontinue;}return1;}matlab代码实现functionKruskal(w,MAX)%此程序为最小支撑树的Kruskal算法实现%w为无向图的距离矩阵，故为对称矩阵%MAX为距离矩阵中∞的实际输入值%时间：2011年6月22日0:07:53len=length(w);%图的点数edge=zeros(len*(len-1）,3）;%用于存储图中的边count=1;%图中的边数fori=1:len-1%循环距离矩阵，记录存储边forj=i+1:lenifw(i,j)~=MAXedge(count,1）=w(i,j);edge(count,2）=i;edge(count,3）=j;count=count+1;endendendedge=edge（1:count-1,:);%去掉无用边[tmp,index]=sort(edge(:,1）);%所有边按升序排序i=3;%其实测试边数为3条（3条以下无法构成圈，即无需检测）while1x=findcycle(edge(index（1:i),:),len);%检测这些边是否构成圈ifxindex(i)=0;%若构成圈，则将该边对应的index项标记为0，以便除去elsei=i+1;%若没有构成圈，则i加1，加入下一边检测endindex=index(index>0);%将构成圈的边从index中除去ifi==lenbreak;%找到符合条件的点数减一条的边，即找到一个最小支撑树endendindex=index（1:len-1）;%截短index矩阵，保留前len-1项%%%%%%%%%%%%结果显示%%%%%%%%%%%%%s=sprintf('\n\t%s\t%s\t%s\t','边端点','距离','是否在最小支撑树');fori=1:count-1edge_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）,'√');elses_tmp=sprintf('\n\t(%d,%d)\t%d\t%s\t',edge_tmp（2）,edge_tmp（3）,edge_tmp（1）,'×');ends=strcat(s,s_tmp);enddisp(s);endfunctionisfind=findcycle(w,N)%本程序用于判断所给的边能否构成圈：有圈，返回1；否则返回0%w：输入的边的矩阵%N：原图的点数%原理：不断除去出现次数小于2的端点所在的边，最后观察是否有边留下len=length(w(:,1）);index=1:len;while1num=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;endindex_tmp=zeros（1,num);%记录除去出现次数小于2的端点所在的边的边的下标集合discard=find(p<2）;%找到出现次数小于2的端点count=0;%记录剩余的边数fori=1:num%判断各边是否有仅出现一次端点——没有，则记录其序号于index_tmpif~(~isempty(find(discard==w(index(i),2）,1）)||~isempty(find(discard==w(index(i),3）,1）))count=count+1;index_tmp(count)=index(i);endendifnum==count%当没有边被被除去时，循环停止index=index_tmp（1:count);%更新indexbreak;elseindex=index_tmp（1:count);%更新indexendendifisempty(index)%若最后剩下的边数为0，则无圈isfind=0;elseisfind=1;endend%%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<n(n-1）/2）}constmaxn=100;maxe=maxn*maxn;typeedge=recorda,b:integer;maxe]ofedge;maxn]ofinteger;en;i:=l;j:=r;repeatwhileedges[i].len<xdoinc(i);whileedges[j].len>xdodec(j);ifi<=jthenbeginswap(i,j);inc(i);dec(j);enduntili>j;ifl<jthenquicksort(l,j);ifi<rthenquicksort(i,r);end;procedureinit;vari:integer;beginassign(input,'');reset(input);readln(n,e);fori:=1toedoreadln(edges[i].a,edges[i].b,edges[i].len);例题详见vijosp1045Kerry的电缆网络typerec=recordx,y:longint;cost:real;end;varf:array[1..1000000]ofrec;s,ans:real;i,n,m,k,dad:longint;father:array[1..1000000]oflongint;procedurekp(l,r:longint);vari,j:longint;xx:real;y:rec;begini:=l;j:=r;xx:=f[(i+j)div2].cost;repeatwhilexx>f[i].costdoinc(i);whilexx<f[j].costdodec(j);ifi<=jthenbeginy:=f[i];f[i]:=f[j];f[j]:=y;inc(i);dec(j);end;untili>j;ifi<rthenkp(i,r);ifl<jthenkp(l,j);end;functionfind(x:longint):longint;beginiffather[x]=xthenexit(x);father[x]:=find(father[x]);exit(father[x]);end;procedureunion(x,y:longint;j:real);beginx:=find(x);y:=find(y);ifx<>ythenbeginfather[y]:=x;ans:=ans+j;inc(k);end;end;beginreadln(s);readln(n);m:=0;whilenoteofdobegininc(m);withf[m]doreadln(x,y,cost);end;ifm<n-1thenbeginwriteln('Impossible');exit;end;fori:=1tondofather[i]:=i;kp（1,m);k:=0;fori:=1tomdobeginifk=n-1thenbreak;union(f[i].x,f[i].y,f[i].cost);end;ifk<n-1thenbeginwriteln('Impossible');exit;end;ifans>sthenwriteln('Impossible')elsewriteln('Need',ans:0:2,'milesofcable');end.Kruskal算法适用于边稀疏的情形，而Prim算法适用于边稠密的情形其它最小生成树算法c++代码实现#include<>#include<>#include<vector>usingnamespacestd;#defineMAXNUM_VERTEX20=a;[j].w=c;[j].weight=d;}elsegotop1;}}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<int>&array){for(inti=0;i<();i++)array[i]=i;}intfindset(vector<int>&parent,inti){if(i!=parent[i])i=parent[i];returni;}inlinevoidmerge(vector<int>&parent,inti,intj){parent[i]=j;}/*不相交集处理函数*/voidkruskal(){intnum_ver=;intcount=0;vector<int>parent_ver;(num_ver);/*核心部分是用不相交集合成树*/makeset(parent_ver);printf("theedgeofmintreeasfollow:\n");for(inti=0;i<num_ver&&count<num_ver-1;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();kruskal();}java代码实现importimportclassBianimplementsComparablealue1:(value==((Bian)arg0).value0:-1）;}@OverridepublicStringtoString(){return"Bian[first="+first+",second="+second+",value="+value+"]";}}clas