通过使用prim算法(反圈法)求解最小支撑树问题..

《通过使用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)　三．

2、使用环境WindowsXP环境下MATLAB编写四．调试过程程序如下:#include#include#include#defineINFINITY1000#definemax_name50#definemax_vertex_num50typedefcharvertex[max_name];//顶点名字串typedefintadjMatrix[max_vertex_num][max_vertex_num];//邻接距阵typedefstruct{vertexadjvex;//邻接矩阵

3、intlowcost;//权值}close[max_vertex_num];//定义一个结构以便在后面closedge使用typedefstruct//定义图{vertexvexs[max_vertex_num];//顶点集adjMatrixarcs;//边intvexnum,arcnum;//点个数，边个数}MGraph;intLocateVex(MGraphG,vertexu)//若G中存在顶点u,则返回该点在图中位置;否则返回其他信息;{inti;for(i=0;i

4、)==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;i

5、s[i][j]=INFINITY;printf("输入一条边依附的顶点及权值：",G.arcnum);//输入一条边依附的顶点及权值for(k=0;k

6、ITY;//初始化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.vexnum;++j)//辅助数组初始化closedge从O开始{if

7、(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;i

8、LocateVex(G,closedge[k].adjvex)]);//输出生成树的边closedge[k].lowcost=0;//第k个顶点并入U集flag[count]=k