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

1、kruskal算法及代码-含伪代码、c代码、matlab、pascal等代码K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。目录Kruskal算法 1. 算法定义 2. 举例描述Kruskal算法的代码实现 1. 伪代码 2. C代码实现 3. matl

2、ab代码实现 4. pascal代码实现Kruskal算法 1. 算法定义 2. 举例描述Kruskal算法的代码实现 1. 伪代码 2. C代码实现 3. matlab代码实现 4. pascal代码实现算法定义克鲁斯卡尔算法 假设 WN=(V,E) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；

3、反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。 举例描述克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程可以用一个图来表示。这里的图的选择借用了Wikipedia上的那个。非常清晰且直观。 首先第一步，我们有一张图，有若干点和边 如下图所示： 1 / 22 第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的

4、资源进行选择。 排序完成后，我们率先选择了边AD。这样我们的图就变成了 第二步，在剩下的变中寻找。我们找到了CE。这里边的权重也是5 依次类推我们找到了6,7,7。完成之后，图变成了这个样子。 . 下一步就是关键了。下面选择那条边呢？ BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。 最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是下图： . 到这里所有的边点都已经连通了，一个最小

5、生成树构建完成。 编辑本段Kruskal算法的代码实现伪代码MST-KRUSKAL(G，w) C代码实现/* Kruskal.c Copyright (c) 2002,2006 by ctu_85 All Rights Reserved. */ /* I am sorry to say that the situation of unconnected graph is not concerned */ #include "stdio.h" #define maxver 10 #define maxright 100 int Gmaxvermaxver,record=0,t

6、ouchedmaxvermaxver; int circle=0; int FindCircle(int,int,int,int); int main() int pathmaxver2,usedmaxvermaxver; int i,j,k,t,min=maxright,exsit=0; int v1,v2,num,temp,status=0; restart: printf("Please enter the number of vertex(s) in the graph:n"); scanf("%d",&num); if(num>m

7、axver|num<0) printf("Error!Please reinput!n"); goto restart; for(j=0;j<num;j+) for(k=0;k<num;k+) if(j=k) Gjk=maxright; usedjk=1; touchedjk=0; else if(j<k) re: printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:n",j+1,k+1）;

8、 scanf("%d",&temp); if(temp>=maxright|temp<-1） printf("Invalid input!n"); goto re; if(temp=-1） temp=maxright; Gjk=Gkj=temp; usedjk=usedkj=0; touchedjk=touchedkj=0; for(j=0;j<num;j+) pathj0=0; pathj1=0; for(j=0;j<num;j+) status=0; for(k=0;k<num;k+) if(Gjk<max

9、right) 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(Gjk<min&&!usedjk) v1=j; v2=k; min=Gjk; if(!usedv1v2) usedv1v2=1; usedv2v1=1; touchedv1v2=1; touchedv2v1=1; path0=v1; path1=v2; for(t=0;t<record;t+) FindCircle

10、(patht0,patht0,num,patht0); if(circle) /*if a circle exsits,roll back*/ circle=0; i-; exsit=0; touchedv1v2=0; touchedv2v1=0; min=maxright; else record+; min=maxright; if(!status) printf("We cannot deal with it because the graph is not connected!n"); else for(i=0;i<num-1;i+) printf("

11、;Path %d:vertex %d to vertex %dn",i+1,path0+1,path1+1）; return 1; int FindCircle(int start,int begin,int times,int pre) /* to judge whether a circle is produced*/ int i; for(i=0;i<times;i+) if(touchedbegin=1） if(i=start&&pre!=start) circle=1; return 1; break; else if(pre!=i) FindCirc

12、le(start,i,times,begin); else continue; return 1; matlab代码实现function Kruskal(w,MAX) %此程序为最小支撑树的Kruskal算法实现 %w为无向图的距离矩阵，故为对称矩阵 %MAX为距离矩阵中的实际输入值 %时间：2011年6月22日0:07:53 len=length(w); %图的点数 edge=zeros(len*(len-1）,3）; %用于存储图中的边 count=1; %图中的边数 for i=1:len-1 %循环距离矩阵，记录存储边 for j=i+1:len if w(i,j)=MAX edge(

13、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条以下无法构成圈，即无需检测） while 1 x=findcycle(edge(index（1:i),:),len); %检测这些边是否构成圈 if x index(i)=0; %若构成圈，则将该边对应的index项标记为0，以便除去 else i=i+1; %若没有构成

14、圈，则i加1，加入下一边检测 end index=index(index>0); %将构成圈的边从index中除去 if i=len break; %找到符合条件的点数减一条的边，即找到一个最小支撑树 end end index=index（1:len-1）; %截短index矩阵，保留前len-1项 % 结果显示 % s=sprintf('nt%st%st %st','边端点','距离','是否在最小支撑树'); for i=1:count-1 edge_tmp=edge(i,:); if isempty(find(ind

15、ex=i,1）) s_tmp=sprintf('n t (%d,%d)t %dt %st',edge_tmp（2）,edge_tmp（3）,edge_tmp（1）,''); else s_tmp=sprintf('n t (%d,%d)t %dt %st',edge_tmp（2）,edge_tmp（3）,edge_tmp（1）,'×'); end s=strcat(s,s_tmp); end disp(s); end function isfind=findcycle(w,N) %本程序用于判断所给的边能否构成圈：有圈，

16、返回1；否则返回0 %w：输入的边的矩阵 %N：原图的点数 %原理：不断除去出现次数小于2的端点所在的边，最后观察是否有边留下 len=length(w(:,1）); index=1:len; while 1 num=length(index); %边数 p=zeros（1,N); %用于存储各点的出现的次数（一条边对应两个端点） for i=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); %记录除去出现次

17、数小于2的端点所在的边的边的下标集合 discard=find(p<2）; %找到出现次数小于2的端点 count=0; %记录剩余的边数 for i=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 if num=count %当没有边被被除去时，循环停止 index=index_tmp（1

18、:count); %更新index break; else index=index_tmp（1:count); %更新index end end if isempty(index) %若最后剩下的边数为0，则无圈 isfind=0; else isfind=1; end end % % a = % 0 3 2 3 100 100 100 % 3 0 2 100 100 100 6 % 2 2 0 3 100 1 100 % 3 100 3 0 5 100 100 % 100 100 100 5 0 4 6 % 100 100 1 100 4 0 5 % 100 6 100 6 100 5 0;

19、 % % 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） const maxn=100; maxe=maxn*maxn; type edge=

20、record a,b :integer; /边的2个顶点 len :integer; /边的长度 end; var edges :array0.maxeof edge; /保存所有边的信息 p,r :array0.maxnof integer; /p保存i的父亲节点，r用来实现Union-Find的rank启发式 n,e :integer; /n为顶点数，e为边数 procedure swap(a,b:integer); /交换 begin edges0:=edgesa; edgesa:=edgesb; edgesb:=edges0; end; procedure quicksort(l,r:

21、integer); /快速排序 var x,i,j :integer; begin x:=edgesrandom(r-l+1）+l.len; i:=l;j:=r; repeat while edgesi.len<x do inc(i); while edgesj.len>x do dec(j); if i<=j then begin swap(i,j); inc(i);dec(j); end until i>j; if l<j then quicksort(l,j); if i<r then quicksort(i,r); end; procedure in

22、it; var i :integer; begin assign(input,'g.in');reset(input); readln(n,e); for i:=1 to e do readln(edgesi.a,edgesi.b,edgesi.len); /从文件读入图的信息 for i:=1 to n do pi:=i; /初始化并查集 randomize; quicksort（1,e); /使用快速排序将边按权值从小到大排列 end; function find(x:integer):integer; /并查集的Find，用来判断2个顶点是否属于一个连通分量 begin

23、if x<>px then px:=find(px); find:=px end; procedure union(a,b:integer); /如果不属于且权值最小则将2个顶点合并到一个连通分量 var t :integer; begin a:=find(a);b:=find(b); if ra>rb then begin t:=a;a:=b;b:=t end; if ra=rbthen inc(ra); pa:=b; end; procedure kruskal; /主过程 var en :integer; /en为当前边的编号 count :integer; /统计进行

24、了几次合并。n-1次合并后就得到最小生成树 tot :integer; /统计最小生成树的边权总和 begin count:=0;en:=0; tot:=0; while count<n-1 do begin inc(en); with edgesen do begin if find(a)<>find(b) then begin union(a,b); writeln(a,'-',b,':',len); inc(tot,len); inc(count); end; end; end; writeln('Total Length=

25、9;,tot) end; =main= begin init; kruskal; end. 例题详见 vijos p1045 Kerry 的电缆网络 type rec=record x,y:longint; cost:real; end; var f:array1.1000000 of rec; s,ans:real; i,n,m,k,dad:longint; father:array1.1000000 of longint; procedure kp(l,r:longint); var i,j:longint; xx:real; y:rec; begin i:=l; j:=r; xx:=f(

26、i+j) div 2.cost; repeat while xx>fi.cost do inc(i); while xx<fj.cost do dec(j); if i<=j then begin y:=fi; fi:=fj; fj:=y; inc(i); dec(j); end; until i>j; if i<r then kp(i,r); if l<j then kp(l,j); end; function find(x:longint):longint; begin if fatherx=x then exit(x); fatherx:=find(f

27、atherx); exit(fatherx); end; procedure union(x,y:longint;j:real); begin x:=find(x); y:=find(y); if x<>y then begin fathery:=x; ans:=ans+j; inc(k); end; end; begin readln(s); readln(n); m:=0; while not eof do begin inc(m); with fm do readln(x,y,cost); end; if m<n-1 then begin writeln('Im

28、possible'); exit; end; for i:=1 to n do fatheri:=i; kp（1,m); k:=0; for i:=1 to m do begin if k=n-1 then break; union(fi.x,fi.y,fi.cost); end; if k<n-1 then begin writeln('Impossible'); exit; end; if ans>s then writeln('Impossible') else writeln('Need ',ans:0:2,'

29、 miles of cable'); end. Kruskal算法适用于边稀疏的情形，而Prim算法适用于边稠密的情形 其它最小生成树算法 c+代码实现 #include <stdio.h> #include <stdlib.h> #include <vector> using namespace std; #define MAXNUM_VERTEX 20 /最多有 20个顶点 #define MAXNUM_EDGE 21 typedef struct int v,w; int weight; Edge; typedef struct int ver

30、texMAXNUM_VERTEX; Edge edgeMAXNUM_EDGE; int num_vertex,num_edge; Graph; Graph graph; /声明为全局变量 bool search_vertex(int ver) for(int i=0; i<graph.num_vertex; i+) if( ver = graph.vertexi ) return 1; printf("the vertex %d you input is not existed! n",ver); return 0; void create_graph() /输入顶点

31、信息 printf("input the number of vertex in the graphn"); scanf(" %d",&graph.num_vertex); printf("input the vertex of graph,like 1,2n"); for(int i=0; i<graph.num_vertex; i+) scanf(" %d",&graph.vertexi); /输入边信息 printf("input the number of edge in t

32、he graphn"); scanf(" %d",&graph.num_edge); printf("intput the edge of graph and the weight of line,like 1-2 5n"); for(int j=0; j<graph.num_edge; j+) p1:int a,c,d; char b; scanf(" %d %c %d %d",&a,&b,&c,&d); if( search_vertex(a) && sear

33、ch_vertex(c) ) graph.edgej.v=a; graph.edgej.w=c; graph.edgej.weight=d; else goto p1; void sort_by_weight() for(int i=1; i<graph.num_edge; i+) Edge temp=graph.edgei; for(int j=i-1; j>=0 && graph.edgej.weight>temp.weight; j-) graph.edgej+1=graph.edgej; graph.edgej+1=temp; /*不相交集处理函数*/

34、 inline void makeset(vector<int> & array) for(int i=0; i<array.size(); i+) arrayi=i; int findset(vector<int> & parent,int i) if(i != parenti) i=parenti; return i; inline void merge(vector<int> & parent,int i,int j) parenti=j; /*不相交集处理函数*/ void kruskal() int num_ver=g

35、raph.num_vertex; int count=0; vector<int> parent_ver; parent_ver.resize(num_ver); /*核心部分是用不相交集合成树*/ makeset(parent_ver); printf("the edge of min tree as follow: n"); for( int i=0; i<num_ver && count<num_ver-1; i+ ) /count表示合并（merge）的次数num_ver-1次 int m=graph.edgei.v; int

36、 n=graph.edgei.w; int w=graph.edgei.weight; if( findset(parent_ver,m) != findset(parent_ver,n) /当属于不同的集合时，则将该边添加进树中 printf("(%d %d) %dn",m,n,w); merge(parent_ver,m,n); count+; void print_edge() printf("the graph you input as follow: n"); for(int i=0; i<graph.num_edge; i+) prin

37、tf("%d-%d the weight is: %dn",graph.edgei.v,graph.edgei.w,graph.edgei.weight); void main() create_graph(); sort_by_weight(); print_edge(); kruskal(); java代码实现 import java.util.ArrayList; import java.util.Collections; class Bian implements Comparable / 两点之间的加权边 private int first,second;/ 表示

38、一条边的两个节点 private int value;/ 权值 public Bian(int first,int second,int value) this.first = first; this.second = second; this.value = value; public int getFirst() return first; public int getSecond() return second; public int getValue() return value; Override public int compareTo(Object arg0) return va

39、lue > (Bian) arg0).value 1 : (value = (Bian) arg0).value 0 : -1）; Override public String toString() return "Bian first=" + first + ",second=" + second + ",value=" + value + "" class ShuZu static ArrayList<ArrayList> list = new ArrayList<ArrayList&g

40、t;();/ 存放每一个数组中的节点的数组 static ArrayList<ArrayList> bianList = new ArrayList<ArrayList>();/ 对应存放数组中的边的数组 public static void check(Bian b)/ 检查在哪个数组中 if (list.size() = 0) ArrayList<Integer> sub = new ArrayList<Integer>(); sub.add(b.getFirst(); sub.add(b.getSecond(); list.add(sub)

41、; ArrayList<Bian> bian = new ArrayList<Bian>(); bian.add(b); bianList.add(bian); return; int first = b.getFirst(); int shuyu1 = -1; int second = b.getSecond(); int shuyu2 = -1; for (int i = 0; i < list.size(); i+)/ 检查两个节点分别属于哪个数组 for (int m = 0; m < list.get(i).size(); m+) if (first = (Integer) list.get(i).get(m) shuyu1 = i; if (second = (Integer) list.get(i).get(m) shuyu2 = i; if (shuyu1 = -1 && shuyu2 = -1）/ 表示这两个节点都没有需要新加入 ArrayList<Integer> sub = new ArrayList<Integer>(); sub.add(b.getFirst(); sub.add(b.getSecond(); list.add(sub); Arra