以邻接矩阵存储的图类型构造n个城市连接的最小生成树.doc

《以邻接矩阵存储的图类型构造n个城市连接的最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、以邻接矩阵存储的图类型构造n个城市连接的最小生成树代码：#include#include#defineMaxVextexNum30/*最大顶点数为30*/#defineINFINITY32767/*定义一个权值的最大值*/typedefstruct{intvexs[MaxVextexNum];/*顶点表*/intarcs[MaxVextexNum][MaxVextexNum];/*邻接矩阵，即边表*/intn,e;/*顶点数和边数*/}MGraph;/*MGragh是以邻接矩阵存储的图类型*/typede

2、fstruct{intadjvertex;/*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/intlowcost;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/}ClosEdge[MaxVextexNum];/*用prim算法求最小生成树时的辅助数组*/voidCreatGraph(MGraph*G)/*建立有向图G的邻接矩阵存储*/{inti,j,k,w;printf("请输入顶点数和边数ne:");scanf("%d%d",&(G->n),&(G->e));/*输入顶点数和边数*/printf("请输顶点字符信息(

3、共%d个)：",G->n);for(i=0;in;i++){scanf("%d",&(G->vexs[i]));/*输入顶点信息，建立顶点表*/}for(i=0;in;i++)for(j=0;jn;j++){if(i==j){G->arcs[i][j]=0;}elseG->arcs[i][j]=INFINITY;}/*初始化邻接矩阵32767为无穷大*/printf("请输入边对应的顶点序号(共%d对)，以及权值:",G->e);for(k=0;ke;k++){scanf("%d%d%d"

4、,&i,&j,&w);/*输入e条边，建立邻接矩阵*/G->arcs[i][j]=w;/*若加入G->edges[j][i]=1，则为无向图的邻接矩阵*/G->arcs[j][i]=w;}printf("此连邻接矩阵为（32767为无穷大）：");for(i=0;in;i++){for(j=0;jn;j++)printf("%8d",G->arcs[i][j]);printf("");}}voidMiniSpanTree_PRIM(MGraphG,intu,ClosEdgeclosedge){/*从第u个顶点出发构造图

5、G的最小生成树，最小生成树顶点信息存放在数组closedge中*/inti,j,w,k,cost=0;for(i=0;i

6、/if(closedge[j].lowcost!=0&&closedge[j].lowcost

7、树中包括的城市间的道路:");for(i=0;i%d,%d",i,closedge[i].adjvertex,G.arcs[i][closedge[i].adjvertex]);cost=cost+G.arcs[i][closedge[i].adjvertex];}printf("最小生成树的代价为:%d",cost);}intmain(){intt;MGraphG;ClosEdgeclosedge;CreatGraph(&G);pr

8、intf("请输入源点：");scanf("%d",&t);MiniSpanTree_PRIM(G,t,closedge);return1;}结果：（总结：在做课程