欢迎来到天天文库
浏览记录
ID:18728491
大小:84.50 KB
页数:7页
时间:2018-09-21
《通过使用prim算法(反圈法)求解最小支撑树问题..》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、一.实验目的通过使用prim算法(反圈法)求解最小支撑树问题..二.实验内容设图G=(V,E),其生成树的顶点集合为U。 ①.把v0放入U。 ②.在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树。 ③.把②找到的边的v加入U集合。如果U集合已有n个元素,则结束,否则继续执行②。 其算法的时间复杂度为O(n^2) Prim算法实现:图用邻接阵表示,路径不通用无穷大表示,在计算机中可用一个大整数代替。采用堆,可以将复杂度降为O(mlogn),如果采用Fibonaci堆可以将复杂度降为O(nlogn+m) 三.使用环境WindowsXP环境下M
2、ATLAB编写四.调试过程程序如下:#include#include#include#defineINFINITY1000#definemax_name50#definemax_vertex_num50typedefcharvertex[max_name];//顶点名字串typedefintadjMatrix[max_vertex_num][max_vertex_num];//邻接距阵typedefstruct{vertexadjvex;//邻接矩阵intlowcost;//权值}close[max_vertex_n
3、um];//定义一个结构以便在后面closedge使用typedefstruct//定义图{vertexvexs[max_vertex_num];//顶点集adjMatrixarcs;//边intvexnum,arcnum;//点个数,边个数}MGraph;intLocateVex(MGraphG,vertexu)//若G中存在顶点u,则返回该点在图中位置;否则返回其他信息;{inti;for(i=0;i4、i,j,k,w;vertexv1,v2;printf("输入无向图顶点数和边数:");scanf("%d%d",&G.vexnum,&G.arcnum);printf("输入各顶点的值:",G.vexnum);for(i=0;i5、for(k=0;k0){min=c6、[j].lowcost;k=j;}returnk;}voidPRIM(MGraphG,vertexu){inti,j,k=0;closeclosedge;//一个结构boolisbreak=false;k=LocateVex(G,u);//u在图中位置返回G.vexs[i]中下标for(j=0;j<=G.vexnum;++j)//辅助数组初始化closedge从O开始{if(j!=k)//没有自己到自己的closedge[k].lowcost=0;strcpy(closedge[j].adjvex,u);closedge[j].lowcost=G.arcs[k][j];//7、列}intflag[1000];flag[0]=0;intcount=1;for(i=1;i
4、i,j,k,w;vertexv1,v2;printf("输入无向图顶点数和边数:");scanf("%d%d",&G.vexnum,&G.arcnum);printf("输入各顶点的值:",G.vexnum);for(i=0;i5、for(k=0;k0){min=c6、[j].lowcost;k=j;}returnk;}voidPRIM(MGraphG,vertexu){inti,j,k=0;closeclosedge;//一个结构boolisbreak=false;k=LocateVex(G,u);//u在图中位置返回G.vexs[i]中下标for(j=0;j<=G.vexnum;++j)//辅助数组初始化closedge从O开始{if(j!=k)//没有自己到自己的closedge[k].lowcost=0;strcpy(closedge[j].adjvex,u);closedge[j].lowcost=G.arcs[k][j];//7、列}intflag[1000];flag[0]=0;intcount=1;for(i=1;i
5、for(k=0;k0){min=c
6、[j].lowcost;k=j;}returnk;}voidPRIM(MGraphG,vertexu){inti,j,k=0;closeclosedge;//一个结构boolisbreak=false;k=LocateVex(G,u);//u在图中位置返回G.vexs[i]中下标for(j=0;j<=G.vexnum;++j)//辅助数组初始化closedge从O开始{if(j!=k)//没有自己到自己的closedge[k].lowcost=0;strcpy(closedge[j].adjvex,u);closedge[j].lowcost=G.arcs[k][j];//
7、列}intflag[1000];flag[0]=0;intcount=1;for(i=1;i
此文档下载收益归作者所有