西安电子科技大学离散数学大作业

西安电子科技大学离散数学大作业西安电子科技大学离散数学大作业西安电子科技大学离散数学大作业西安电子科技大学离散数学大作业编制仅供参考审核批准生效日期地址：电话：传真:邮编:离散数学大作业班级：021231学号：02123120姓名：题目：编程实现赋权有向图的最小生成树摘要求解图的最小生成树有三种算法，分别为Prim算法、Kruskal算法和Boruvka算法。这三种算法都是贪心算法。所以本次实验分别使用Kruskal算法和Prim算法实现赋权有向图的最小生成树。Kruskal算法基本思想为：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。具体作法如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。Prim算法基本思想是：首先选取图中任意一个顶点v作为生成树的根，之后继续往生成树中添加顶点w，则在顶点w和顶点v之间必须有边，且该边上的权值应在所有和v相邻接的边中属最小。关键词：邻接矩阵；邻接表；Kruskal算法；Prim算法；最小生成树一、最小生成树的研究进展最小生成树可以使用Kruskal算法和Prim算法。下面具体介绍这两种算法。Kruskal算法求加权连通图的最小生成树的算法。kruskal算法总共选择n-1条边，（共n条边）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。该算法的时间复杂度为O(elge);Kruskal算法的时间主要取决于边数,它较适合于稀疏图。Kruskal算法构造最小生成树的过程图解:Prim算法Prim算法可以说是所有MST算法中最简单的，比较适用于稠密图。以图中任意一个顶点S开始，选择与之相关连的边中权值最小的边加入到MST中，假设这条边的终点为T，则MST初始化为(S,T)，称之为“当前MST”。接下来在剩余的边中选择与当前MST中s所有顶点相关连的边中权值最小的边，并添加到当前MST中。这一过程一直迭代到图中所有顶点都添加到MST中为止。从连通网络N={V,E}中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集。prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。二、最小生成树的实现Kruskal算法关键部分的实现Kruskal算法的计算流程大致如下：1.将无向图的边按距离长短递增式排序，放到集合中2.遍历该集合，找出最短的边，加入到结果生成树的集合中3.如果结果生成树出现回路，则放弃这条边4.重新执行步骤2，直至所有顶点被遍历可以看出在每次遍历过程中采用了贪心算法Kruskal算法代码如下：dj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=;++i)acrvisited[i]=0;for(j=0;j!=;++j){m=10000;for(i=0;i!=;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}buf=find(acrvisited,x);edf=find(acrvisited,y);edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}dj=int_max;[i][j].info=NULL;}for(intk=0;k!=;++k){cout<<"输入一条边依附的顶点和权:例如abc(a,b表示顶点，c表示权)"<<endl;cin>>v1>>v2>>w;dj=w;[j][i].adj=w;}cout<<"图G邻接矩阵创建成功！"<<endl;return;}intvisited[max];ata=[i];[i].firstarc=NULL;}for(i=0;i!=;++i){for(j=0;j!=;++j){if[i].firstarc==NULL){if[i][j].adj!=int_max&&j!={arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;while[i][j].adj!=int_max&&j!={tem=(arcnode*)malloc(sizeof(arcnode));tem->adjvex=j;[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if[i][j].adj!=int_max&&j!={arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}=;=;return1;}intfirstadjvex(algraphgra,vnodev)dj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=;++i)acrvisited[i]=0;for(j=0;j!=;++j){m=10000;for(i=0;i!=;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}buf=find(acrvisited,x);edf=find(acrvisited,y);edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}dj;cout<<"prim:"<<endl;prim(g,d);break;case1:cout<<"kruscal:"<<endl;kruscal_arc(G,gra);