数据结构实验六

1、实验六实验名称图及其应用实验性质设计性实验学时数 6学时、实验目的1. 掌握图的存储结构及其实现。2. 掌握图的深度和广度遍历算法及其实现。3掌握图的常见算法的思想及应用。、实验内容1. 实现对无向图的存储和遍历等操作。2. 最小生成树问题。Z三、实 验 过 程1、实验题目 问题描述以下题目根据自己兴趣和能力可选作一道作为实验题目：（1） 使用邻接表或邻接矩阵存储一个无向图，实现对其进行深度和广度遍历的 操作；（2）n个城市之间建立通信联络网，最多可能设置 n（n-1）/2 条线路，那么, 如何在这些可能的线路中选择 n-1条，以使总的耗费最少。使用最小生成树实 现解决此问题。（3）根据一张自

2、驾游旅游路线图，可以知道城市间的高速公路长度以及该公路 要收取的过路费。现在编写一个程序，找出一条出发地和目的地之间的最短路 径。如果有若干条路径都是最短的，那么需要输出过路费最少的一条路径。基本要求（1）按实验内容编写完整的程序，并上机验证。（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据。2、源程序(1)#in clude#in cludevstdio.hin t visited20;typ edef struct ArcNodeint adj; ArcNode;typ edef structin t vert

3、ex20;ArcNode arc2020;int vex nu m,arc num;AdjMatrix;创建一个有向网*/void Create(AdjMatrix *G) /* int i,j,k, n,e;printf(请输入图中顶点的个数和边数:);scan f(%d%d,&n,&e);G-vex num=n;G-arc num=e;printf(请输入各顶点的值:);for (i=0;ivex nu m;i+)sca nf(%d,&G-vertexi);for (i=0;ivex nu m;i+) for(j=0;jvex nu m;j+) G-arcij.adj=0;printf(请

4、输入有关联的两个顶点的下标:n);for (k=0;karc nu m;k+)scan f(%d%d,&i,&j);G-arcij.adj=1;G-arcji.adj=1;/*图g为邻接矩阵类型void De pthFristSearch(AdjMatrix g, i nt i) AdjMatrix */ int j;prin tf(%d,g.vertexi);visitedi=1;for (j=0;jvg.vex nu m;j+)if (!visitedj&g.arcij.adj=1)Dep thFnstSearch(g,j);void TraverseGra ph(AdjMatrix g) int i;for(i=0;ig.vex nu m;i+) visitedi=0;for(i=0;ig.vex nu m;i+) if(!visitedi)Dep thFristSearch(g,i);int mai n() / 主函数 int i,j;AdjMatrix g;Create(&g);printf(输出关系二维矩阵:);for(i=0;ig.vex nu m;i+)for (j=0;jg.vex nu m;j+)prin tf(%d,g.arcij.adj);prin