计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Pag e 1 o f 18 题5.3 图遍历的演示 实习报告 题目:试设计一个程序,演示在连通的无向图上访问全部结点的操作 一、需求分析 1、以邻接多重表为存储结构； 2、实现连通和非连通的无向图的深度优先和广度优先遍历； 3、要求利用栈实现无向图的深度优先遍历； 4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集； 5、用凹入表打印生成树； 6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径； 6、本程序用 C++语言编写，在Visial C++ 6.0环境下通过。 二、概要设计 1、设定图的抽象数据类型: ADT Graph{ 数据对象 V:V 是具有相同特性的数据元素的集合,称为点集. 数据关系R: R={VR} VR={(v,w)|v,w 属于V,(v,w)表示v 和 w 之间存在的路径} 基本操作P: CreatGraph(&G,V,VR) 初始条件:V 是图的顶点集,VR 是图中弧的集合. 操作结果:按V 和 VR 是定义构造图G. DestroyGraph(&G) 初始条件:图G 存在 操作结果:销毁图G LocateVex(G,u) 初始条件: 图G 存在,u 和 G 中顶点有相同的特征 操作结果:若图G 中存在顶点u,则返回该顶点在图中的位置;否则返回其他 信 息 GetVex(G,v) 初始条件: 图G 存在,v 是 G 中顶点 操作结果:返回v 的值 FirstAjvex(G,v) 初始条件: 图G 存在,v 是 G 中顶点 操作结果:返回v 的第 一个邻接顶点,若顶在图中没 有邻接顶点,则返回为空 NextAjvex(G,v,w) 初始条件: 图G 存在,v 是 G 中顶点,w 是 v 的邻接顶点 操作结果:返回v 的下一个邻接顶点,若w 是 v 的最 后 一个邻接顶点,则返回空 DeleteVexx(&G,v) 初始条件: 图G 存在,v 是 G 中顶点 操作结果:删 除 顶点v 已 经其相关的弧 DFSTraverse(G,visit()) 初始条件: 图G 存在,visit 的顶点的应 用函 数 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 2 of 18 操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用visit 函数一次,一旦visit 失败,则操作失败 BFSTraverse(G,visit()) 初始条件: 图G 存在,visit 的顶点的应用函数 操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit 函数一次,一旦visit 失败,则操作失败 }ADT Graph 2、设定栈的抽象数据类型： ADT Stack{ 数据对象：D={ai | ai∈CharSet，...
VIP
