实 验 五 图的遍历及其应用实 现 一 、实验目的 1．熟悉图常用的存储结构。 2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3．会用图的遍历解决简单的实际问题。 二、需求分析 很多问题都是建立在图的遍历的基础上实现的，所以必须有一 个程序能够实现将图进行广度和深度遍历，必须对图的所有节点进行访问。 以无向图为例，以无向图的邻接表和邻接矩阵为存储结构，分别实现对图进行广度和深度遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应的生成树的边集。 三、实验内容 [题目一 ] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一 种操作的具体的函数定义和主函数。 提示： 输入示例 1 2 5 3 4 上 图 的 顶 点 和 边 的 信 息 输 入 数 据 为 ： 5 7 DG A B C D E AB AE BC CD DA DB EC 四 、结构算法模块： typedef struct ArcNode//定义邻接表结构 { int adjvex;//该弧所指向的 顶 点 的 位置 struct ArcNode *nextarc;//指向下一条弧的 指针 }ArcNode; typedef struct VNode//定义顶 点 结构类型 { char data;//存放顶 点 信 息 ArcNode *firstarc;//指向第一条依附于该定点 的 指针 }VNode,Adjlist[MAX_VEX_NUM]; typedef struct ALGraph { Adjlist vertices; int vexnum; int arcnum; }ALGraph; 五、相关函数 设计 Create_DG(ALGraph &G)//创建一个有向图 图 的 邻接链表表示 DFSTraverse(ALGraph G,int vex)//对图 G 做深度优先遍历 BFSTraverse(ALGraph G)//有向图 的 广度遍历，从第 v 个顶 点 出发，v 为顶 点 下标 locatevex(ALGraph G,char v)//图 的 基本操作，寻找顶 点 位置的 下标 DFS(ALGraph G,int v)//从第 v 个顶 点 出发递归地深度优先遍历图 G 六、程序流程图 七 、运行结果截图 最 初 程 序 运 行 界 面 如 下： 创建图：请输入图的顶点数和弧数 输入图的顶点信图的创建 输入图深度优先遍历的起点 深度优先遍历图 广度优先遍历图 结束 输 入 图 的 先 相 关 信 息 后 运 行 结 果 (其 中 深 度 优 先 遍 历 的 ...
