欢迎来到天天文库
浏览记录
ID:7272638
大小:84.50 KB
页数:7页
时间:2018-02-10
《通过使用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堆可以将
2、复杂度降为O(nlogn+m) 三.使用环境WindowsXP环境下MATLAB编写四.调试过程程序如下:#include#include#include#defineINFINITY1000#definemax_name50#definemax_vertex_num50typedefcharvertex[max_name];//顶点名字串typedefintadjMatrix[max_vertex_num][max_vertex_num];//邻
3、接距阵typedefstruct{vertexadjvex;//邻接矩阵intlowcost;//权值}close[max_vertex_num];//定义一个结构以便在后面closedge使用typedefstruct//定义图{vertexvexs[max_vertex_num];//顶点集adjMatrixarcs;//边intvexnum,arcnum;//点个数,边个数}MGraph;intLocateVex(MGraphG,vertexu)//若G中存在顶点u,则返回该点在图中位置;否则返回其
4、他信息;{inti;for(i=0;i5、&G.vexs[i]);for(i=0;i6、=G.arcs[j][i]=w;//置于对称弧}}intminimum(closec,MGraphG)//求出下一个节点第k个顶点{inti=0,j,k,min;min=INFINITY;//初始化k=-1;for(j=0;j<=G.vexnum;j++)//求最小if(c[j].lowcost0){min=c[j].lowcost;k=j;}returnk;}voidPRIM(MGraphG,vertexu){inti,j,k=0;closeclosedge;//一7、个结构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];//列}intflag[1000];flag[0]=0;intcount=1;for(i=1;8、i
5、&G.vexs[i]);for(i=0;i6、=G.arcs[j][i]=w;//置于对称弧}}intminimum(closec,MGraphG)//求出下一个节点第k个顶点{inti=0,j,k,min;min=INFINITY;//初始化k=-1;for(j=0;j<=G.vexnum;j++)//求最小if(c[j].lowcost0){min=c[j].lowcost;k=j;}returnk;}voidPRIM(MGraphG,vertexu){inti,j,k=0;closeclosedge;//一7、个结构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];//列}intflag[1000];flag[0]=0;intcount=1;for(i=1;8、i
6、=G.arcs[j][i]=w;//置于对称弧}}intminimum(closec,MGraphG)//求出下一个节点第k个顶点{inti=0,j,k,min;min=INFINITY;//初始化k=-1;for(j=0;j<=G.vexnum;j++)//求最小if(c[j].lowcost0){min=c[j].lowcost;k=j;}returnk;}voidPRIM(MGraphG,vertexu){inti,j,k=0;closeclosedge;//一
7、个结构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];//列}intflag[1000];flag[0]=0;intcount=1;for(i=1;
8、i
此文档下载收益归作者所有