《数据结构》课件第7章.ppt

G-adjlist[i].firstedge=s;}for(k=1;k=G-e;k++){ /*以边的另一端为起点修改边链表*/i=end[k];j=begin[k];s=(EdgeNode*)malloc(sizeof(EdgeNode));s-adjvex=j;s-next=G-adjlist[i].firstedge;G-adjlist[i].firstedge=s;}printf(邻接表如下：\n);for(i=1;i=G-n;i++){ /*输出邻接表*/printf(%d,G-adjlist[i].vertex);s=G-adjlist[i].firstedge;while(s!=NULL){printf(-%d,s-adjvex);s=s-next;}printf(\n);}}main(){MGraph*s=(MGraph*)malloc(sizeof(MGraph));ALGraph*g=(ALGraph*)malloc(sizeof(ALGraph));intv,e;/*顶点数、边数*/intbegin[MAXLEN],end[MAXLEN];/*各边起点及终点*/inti;printf(“请输入顶点数和边数(输入格式为：顶点数边数)：\n);scanf(%d%d,v,e);for(i=1;i=e;i++){printf(请输入每条边对应的两个顶点的序号(输入格式为：ij)\n);scanf(%d%d,begin[i],end[i]);}CreateMGraph(s,v,e,begin,end);CreateGraphAL(g,v,e,begin,end);}实训7-2最?小?生?成?树【实训目的】1.利用图解决实际生活中一些具体的问题。图7.28居民点示意图2.掌握最小生成树算法。图7.28居民点示意图2.掌握最小生成树算法。【实训内容】假设要在n个居民点之间铺设煤气管道，图7.28画出了各个居民点之间可能的铺设路线，边上的权值代表了铺设此条路线的所需费用。现要求编程求出一种既可以使煤气到达各个居民点之间，又可以使总的造价最低的具体铺设路线。利用C语言编程，掌握图的存储方法及有关图的一些运算方法。【实训要求】1.设计一个程序实现上述过程。2.采用邻接矩阵作为图的存储结构。【算法分析】这是一个求无向连通图的最小生成树T?=?(U，TE)的方法，可以通过前面所学的相关知识来解决具体问题。首先，将图的信息存储在一个邻接矩阵中，然后再调用普里姆算法求最小生成树的函数来求得最后的结果。【程序清单】#defineMAXVEX30#defineMAX1000structvertex{intnum;};typedefstructgraph{structvertexvexs[MAXVEX];intEdges[MAXVEX][MAXVEX];}mgraph;mgraphCreateGraph(int*n) /*建立图的邻接矩阵*/{inti,j,k,w,e;intb,t;mgraphadj;printf(请输入顶点数(n)和边数(e),用逗号分隔;);scanf(%d,%d,n,e);for(i=1;i=*n;i++){adj.vexs[i].num=i;for(j=1;j=*n;j++)adj.Edges[i][j]=MAX;}for(i=1;i=e;i++){adj.vexs[i].num=i;printf(“输入第%d条边的信息：起点,终点及边上的权值,用逗号分隔,i);scanf(%d,%d,%d,b,t,w);adj.Edges[b][t]=w;adj.Edges[t][b]=w;