欢迎来到天天文库
浏览记录
ID:5856411
大小:84.50 KB
页数:7页
时间:2017-12-26
《通过使用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+
2、m) 三.使用环境WindowsXP环境下MATLAB编写四.调试过程程序如下:#include#include#include#defineINFINITY1000#definemax_name50#definemax_vertex_num50typedefcharvertex[max_name];//顶点名字串typedefintadjMatrix[max_vertex_num][max_vertex_num];//邻接距阵typedefstruct{vertexadj
3、vex;//邻接矩阵intlowcost;//权值}close[max_vertex_num];//定义一个结构以便在后面closedge使用typedefstruct//定义图{vertexvexs[max_vertex_num];//顶点集adjMatrixarcs;//边intvexnum,arcnum;//点个数,边个数}MGraph;intLocateVex(MGraphG,vertexu)//若G中存在顶点u,则返回该点在图中位置;否则返回其他信息;{inti;for(i=0;i4、cmp(u,G.vexs[i])==0)returni;return1;}voidCreateGraph(MGraph&G){inti,j,k,w;vertexv1,v2;printf("输入无向图顶点数和边数:");scanf("%d%d",&G.vexnum,&G.arcnum);printf("输入各顶点的值:",G.vexnum);for(i=0;i5、j6、{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;//一个结构boolisbreak=false;k=LocateVex(G,u);//u在图中位置返回G.vexs[i]中下标for(j=0;j<=G.vexnu7、m;++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;i8、edge[k].adjvex,G.vexs[k],G.arcs[k][LocateVex(G,closedge[k].adjvex)]);//输出生成树的边closedge[k].lowcost=0;//第k个顶点并入U集flag[count]=k
4、cmp(u,G.vexs[i])==0)returni;return1;}voidCreateGraph(MGraph&G){inti,j,k,w;vertexv1,v2;printf("输入无向图顶点数和边数:");scanf("%d%d",&G.vexnum,&G.arcnum);printf("输入各顶点的值:",G.vexnum);for(i=0;i5、j6、{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;//一个结构boolisbreak=false;k=LocateVex(G,u);//u在图中位置返回G.vexs[i]中下标for(j=0;j<=G.vexnu7、m;++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;i8、edge[k].adjvex,G.vexs[k],G.arcs[k][LocateVex(G,closedge[k].adjvex)]);//输出生成树的边closedge[k].lowcost=0;//第k个顶点并入U集flag[count]=k
5、j6、{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;//一个结构boolisbreak=false;k=LocateVex(G,u);//u在图中位置返回G.vexs[i]中下标for(j=0;j<=G.vexnu7、m;++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;i8、edge[k].adjvex,G.vexs[k],G.arcs[k][LocateVex(G,closedge[k].adjvex)]);//输出生成树的边closedge[k].lowcost=0;//第k个顶点并入U集flag[count]=k
6、{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;//一个结构boolisbreak=false;k=LocateVex(G,u);//u在图中位置返回G.vexs[i]中下标for(j=0;j<=G.vexnu
7、m;++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;i8、edge[k].adjvex,G.vexs[k],G.arcs[k][LocateVex(G,closedge[k].adjvex)]);//输出生成树的边closedge[k].lowcost=0;//第k个顶点并入U集flag[count]=k
8、edge[k].adjvex,G.vexs[k],G.arcs[k][LocateVex(G,closedge[k].adjvex)]);//输出生成树的边closedge[k].lowcost=0;//第k个顶点并入U集flag[count]=k
此文档下载收益归作者所有