第7章-图

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

第7章图实验图的基本操作及应用一、实验目的1、熟悉图的基本概念,理解图的各种类型2、掌握图的邻接矩阵、邻接表的表示方法3、掌握图的两种遍历方法4、加深理解图的最小生成树的基本思想。5、掌握图的最小生成树的生成方法和实现算法6、加深对图的理解,熟悉图的实际应用二、实验内容(一)验证实验1、图的邻接矩阵表示(二)设计实验1、图的遍历问题案例描述:已知8个城市的交通路线图如下图1所示,从沈阳出发,要到其他7个城市推销产品。给出到达每一个城市的一组城市顺序。图1:8个城市的交通路线图设计方案:图的遍历有深度优先遍历和广度优先遍历两种算法。在这里我们利用数据结构中图的邻接矩阵存储方式以及图的深度优先遍历的算法来解决该问题。结构定义:typedefcharvextype[LEN];typedefintedgetype;沈阳北京天津鞍山大连营口抚顺丹东12637854typedefstruct{vexntypevex[LEN];edgetypearc[VEXN][VEXN];intvexn,arcn;}Mgraph;2、某公司拟建一个局域网,需要连接6栋楼(0,1,2,3,4,5),其地理分布如下图2所示,各边上的权值代表楼宇间距离。设计要求:根据下图中的楼宇分布,设计出布线造价最小的局域网络图,要求连接所有的顶点,并且总的布线费用最低。实验提示:要想布线造价最小,可将图中各顶点间的距离看作其费用。这样就可以用Prim算法构造一棵最小生成树来解决问题。图2图2的邻接矩阵运行时输入数据及运行结果显示如下:Inputvexnum,arcnum:6,10V1,v2,w=0,1,6V1,v2,w=0,2,5V1,v2,w=0,5,1V1,v2,w=1,5,5V1,v2,w=1,3,3V1,v2,w=2,5,5V1,v2,w=2,4,2V1,v2,w=3,5,6V1,v2,w=3,4,6V1,v2,w=4,5,4输出最小生成树中的边及其权值如下:(0,5)1(5,4)4(4,2)2(5,1)5(1,3)35642353120655416∞65∞∞16∞∞3∞55∞∞∞25∞3∞∞66∞∞26∞415564∞参考程序:(一)验证实验1、图的邻接矩阵表示实验程序:#includeStdio.h#includeConio.h#includestdio.h#defineMaxNum50//图的最大顶点数设为50typedefcharVexType[7];//图的顶点类型设为字符数组,2个字符长度typedefintEdgeType;//弧(边)的权值设为整型typedefstruct{VexTypeV[MaxNum];//一维数组存储顶点信息EdgeTypeE[MaxNum][MaxNum];//二维数组表示邻接矩阵,存储边的信息intn,e;//顶点数和边数}MGraph;//图类型定义intLocate(MGraph*G,charvex[])//确定顶点在图G中的位置,即在G-V中的序{inti;for(i=0;iG-n;i++)if(strcmp(G-V[i],vex)==0)returni;}voidCreateGraph(MGraph*G){inti,j,k;charvex1[3],vex2[3];//保存输入的顶点printf(\n输入图的顶点数和边数(用逗号分隔):);scanf(%d,%d,&(G-n),&(G-e));//输入顶点数和边数printf(输入图的顶点信息(最长2个字符):);for(i=0;iG-n;i++){/*G-V[i][0]=G-V[i][1]=0;*/scanf(\n%s,G-V[i]);//输入n个顶点的标识信息,建立顶点数组}for(i=0;iG-n;i++)for(j=0;jG-n;j++)G-E[i][j]=0;//对邻接矩阵元素进行初始化printf(\n输入图中每条边所依附的两个顶点的标识信息:);for(k=0;kG-e;k++)//输入e条边{printf(\n输入第%d条边的第1个顶点:,k+1);scanf(%s,vex1);printf(输入第%d条边的第2个顶点:,k+1);scanf(%s,vex2);//scanf(%s\n%s,vex1,vex2);i=Locate(G,vex1);j=Locate(G,vex2);//scanf(\n%d,%d,&i,&j);//输入每条边所依附的顶点在二维数组中的下标,建立邻接矩阵G-E[i][j]=1;//如果同时输入G-E[j][i]=1;,则是建立无向图的邻接矩阵}}voidPrintGraph(MGraph*G)//打印图的顶点和边的信息{inti,j;printf(\n图中顶点个数为:%d,G-n);printf(\n图中边数为:%d,G-e);printf(\n图中顶点为:);for(i=0;iG-n;i++)printf(%c%c,G-V[i][0],G-V[i][1]);printf(\n图中边为:);for(i=0;iG-n;i++)for(j=0;jG-n;j++)if(G-E[i][j])printf([%c%c,%c%c],G-V[i][0],G-V[i][1],G-V[j][0],G-V[j][1]);}main(){MGraphmg;CreateGraph(&mg);PrintGraph(&mg);}(二)设计实验1、图的遍历问题案例描述:已知8个城市的交通路线图如下图1所示,从沈阳出发,要到其他7个城市推销产品。给出到达每一个城市的一组城市顺序。#defineNULL0#defineVEXN30//顶点的最大个数#defineLEN10//城市名称的最大长度#includestdio.htypedefcharvexntype[LEN];//顶点数据类型typedefintedgetype;//边数据类型typedefstruct{vexntypevex[VEXN];edgetypearc[VEXN][VEXN];intvexn,arcn;//顶点个数和边数}Mgraph;//图的邻接矩阵表示结构intvisit[VEXN];//遍历标志数组MgraphCity_Graph(){inti,j,k;MgraphG;printf(\ninputvexnumber);scanf(%d,&G.vexn);//输入顶点数目printf(inputedgenumbef:);scanf(%d,&G.arcn);//输入总边数printf(input%dvexinformationsuchasShenyangBeijingandsoon:\n,G.vexn);for(i=0;iG.vexn;i++)scanf(%s,&G.vex[i]);for(i=0;iG.vexn;i++)for(j=0;jG.vexn;j++)G.arc[i][j]=0;for(k=0;kG.arcn;k++)//输入各顶点距离{printf(inputedge%dsuchasi,j:,k+1);scanf(%d,%d,&i,&j);while(i1||iG.vexn||j1||jG.vexn)//输入各顶点距离{printf(ErrorvexnNumber,input(i,j)again:);scanf(%d,%d,&i,&j);}G.arc[i-1][j-1]=1;G.arc[j-1][i-1]=1;}returnG;}voidDFS_G(MgraphG,inti)//输出深度优先遍历序列{intj;printf(%s,,G.vex[i]);visit[i]=1;for(j=0;jG.vexn;j++)if((G.arc[i][j]==1)&&(!visit[j]))DFS_G(G,j);}main(){MgraphG;G=City_Graph();//调用输入顶点和边的函数printf(\nDFS:\n);//调用查询最短路径函数DFS_G(G,0);}运行测试:输入Inputvexnumber:8Inputedgenumber:9Input8vexinformationsuchasShenyangBeijingandsoon:沈阳北京天津大连营口鞍山抚顺丹东(输入:每一个顶点回车)Inputedge1suchasi,j:1,2(在英文状态下输入)Inputedge1suchasi,j:1,3Inputedge1suchasi,j:2,3Inputedge1suchasi,j:4,5Inputedge1suchasi,j:5,6Inputedge1suchasi,j:6,7Inputedge1suchasi,j:7,8Inputedge1suchasi,j:1,6Inputedge1suchasi,j:1,7输出DFS:沈阳北京天津鞍山营口大连抚顺丹东2、某公司拟建一个局域网,需要连接6栋楼(0,1,2,3,4,5),其地理分布如下图2所示,各边上的权值代表楼宇间距离。设计要求:根据下图中的楼宇分布,设计出布线造价最小的局域网络图,要求连接所有的顶点,并且总的布线费用最低。实验提示:要想布线造价最小,可将图中各顶点间的距离看作其费用。这样就可以用Prim算法构造一棵最小生成树来解决问题。#defineMAX_VEX50intcreatcost(cost)intcost[][MAX_VEX];//cost这个二维数组用于表示带权图的邻接矩阵{intvexnum,arcnum,i,j,k,v1,v2,w;//输入图的顶点数和狐数或边数printf(inputvexnum,arcnum:);scanf(%d,%d,&vexnum,&arcnum);for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)cost[i][j]=32767;for(k=0;karcnum;k++){printf(v1,v2,w=);scanf(%d,%d,%d,&v1,&v2,&w);//输入所有狐或边的一对顶点v1,v2和权值cost[v1][v2]=w;cost[v2][v1]=w;}return(vexnum);}voidprime(cost,vexnum)intcost[][MAX_VEX],vexnum;//利用普里姆算法产生从顶点v0开始的最小生成树{intlowcost[MAX_VEX],closest[MAX_VEX],i,j,k,min;for(i=0;ivexnum;i++){lowcost[i]=cost[0][i];closest[i]=0;}closest[0]=-1;for(i=1;ivexnum;i++)//从U之外求离U中某一顶点最近的顶点{min=32767;k=0;for(j=0;jvexnum;j++)if(closest[j]!=-1&&lowcost[j]min){min=lowcost[j];k=j;}if(k){printf((%d,%d)%d\n,closest[k],k,lowcost[k]);//输出边及其权值closest[k]=-1;for(j=1;jvexnum;j++)if(closest[j]!=-1&&cost[k][j]lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;//k加入到U中}}}}main(){intvexnum;intcost[MAX_VEX][MAX_VEX];vexnum=creatcost(cost);//建立图的邻接矩阵printf(bianquanzhi:\n);prime(cost,vexnum);}

1 / 7
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功