实验七 最小生成树

《实验七 最小生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验七最小生成树一实验目的1．掌握最小生成树的概念2．掌握Prim算法生成最小生成树的方法3.了解Kruskal算法生成最小生成树的方法二实验内容建立一个无向网，并分别用Prim算法构造最小生成树。三参考程序/*实验7：最小生成树-prim*/#include#include#include#defineINFINITY9999/*无穷大*/#defineMAX_VERTEX_NUM26/*最大顶点数*/#defineMAX_NAME5/*

2、顶点字符串的最大长度*/typedefenum{DG,DN,UDG,UDN}GraphKind;typedefcharVertexType[MAX_NAME];/*顶点类型*/typedefintVRType;/*顶点关系类型*/#defineMAXSIZE100#defineNULL0#defineOK1#defineERROR0typedefintStatus;typedefcharElemType;typedefstruct{VRTypeadj;}Arcclosedgell,AdjMatr

3、ix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧数*/GraphKindkind;/*图的种类标志*/}Mgraph;typedefstruct{VertexTypeadjvex;VRTypelowcost;}minside[MAX_VERTEX_NUM];intLoca

4、teVex(Mgraph*G,VertexTypeu)/*查找顶点u*/{inti;for(i=0;ivexnum;i++)if(strcmp(u,G->vexs[i])==0)returni;return-1;}voidPrintGraph(Mgraph*G)/*输出邻接矩阵存储的图*/{inti,j;printf("%dvexs,%darcs",G->vexnum,G->arcnum);for(i=0;ivexnum;i++)printf("%s",G->vexs[i])

5、;printf("G->arcs.adj");for(i=0;ivexnum;i++){for(j=0;jvexnum;j++)printf("%5d",G->arcs[i][j].adj);printf("");}}voidCreateUDN(Mgraph*G)/*创建无向网*/{inti,j,k,w;VertexTypeva,vb;printf("pleaseentervexnum&&arcnum:");scanf("%d%d",&G->vexnum,&G->ar

6、cnum);printf("pleaseentervertex:");for(i=0;ivexnum;i++)scanf("%s",G->vexs[i]);for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)G->arcs[i][j].adj=INFINITY;printf("enter%darcs:",G->arcnum);for(k=0;karcnum;k++){scanf("%s%s%d%c",va,vb,&w);i=Loca

7、teVex(G,va);j=LocateVex(G,vb);G->arcs[i][j].adj=G->arcs[j][i].adj=w;}G->kind=UDN;}intminimum(minsideSZ,Mgraph*G)/*求SZ.lowcost的最小值，并返回其在SZ中的序号*/{inti=0,j,k,min;while(!SZ[i].lowcost)i++;min=SZ[i].lowcost;k=i;for(j=i+1;jvexnum;j++)if(SZ[j].lowcost>0

8、&&min>SZ[j].lowcost){min=SZ[j].lowcost;k=j;}returnk;}voidPrim(Mgraph*G,VertexTypeu){minsideclosedge;inti,j,k;k=LocateVex(G,u);for(j=0;jvexnum;++j){strcpy(closedge[j].adjvex,u);closedge[j].lowcost=G->arcs[k][j].adj;}closedge[k].lowcost=0;printf("E