《数据结构实验报告》
实验三
1.问题定义及需求分析：
图遍历生成树演示 。通过对连通图和非连通图的遍历，访问图中全部结点。
实验要求
设计图遍历生成树演示程序。采用邻接表和邻接矩阵等存储结构。分别采
用深度优先和广度优先遍历实现。 尝试插入或删除一条边或一个结点的访问
操作。
2.概要设计
抽象数据类型定义：
数据对象 ： 是具有相同特性的数据元素的集合，成为顶点集。
数据关系 ：
且 表示从 到 的弧，谓词 定义了弧
的意义或信息
基本操作
!"#
初始条件： 是图的顶点集， 是图中弧的集合。
操作结果：按 和 的定义构造图 。
$% !"
初始条件：图 已存在。
操作结果：输出图 信息。
" !&' !()*
初始条件：图 存在， 是 中某个顶点。
操作结果：返回 的第一个邻接顶点，若顶点在 中没有邻接顶点则返回“空”。
" !%* !()*
初始条件：图 存在， 是 中某个顶点， 是 的邻接顶点。
操作结果：返回 的（相对于 的）下一个邻接顶点。若 是 的最后一个邻
接点，则返回“空”。
+,! '$'$
初始条件：图 已存在，且为连通图，$'$ 是顶点的应用函数。
操作结果：对图 进行深度优先遍历。在遍历过程中对每个顶点调用函数 $'$
一次且仅一次，一旦 $'$ 失败，则操作失败。
-+,! '$'$
初始条件：图 已存在，且为连通图，$'$ 是顶点的应用函数。
操作结果：对图 进行广度优先遍历。在遍历过程中对每个顶点调用函数 $'$
一次且仅一次，一旦 $'$ 失败，则操作失败。
+, '$'$
初始条件：图 已存在，且为非连通图，$'$ 是顶点的应用函数。
操作结果：对图 进行深度优先遍历。在遍历过程中对每个顶点调用函数 $'$
一次且仅一次，一旦 $'$ 失败，则操作失败。
-+, '$'$
初始条件：图 已存在，且为非连通图，$'$ 是顶点的应用函数。
操作结果：对图 进行广度优先遍历。在遍历过程中对每个顶点调用函数 $'$
一次且仅一次，一旦 $'$ 失败，则操作失败。
.#$)
初始条件：图 已存在，$) 是图 中两个顶点。
操作结果：在 中删除弧$)，若 是无向的，则还删除对称弧)$。
主程序流程及程序模块之间调用关系：
开始
输 入
/
值
输入 值
定 义 结 构 体
' 0
调用 !
"# 构 造
图
否
是
是 否
调用 $% !"
输出图
调用 +,!
'
调用 +,
'
调用 -+,!
'
调用 -+,
'
输 入 要 删
除 的 边
$)
调用 .
#$)
调用 $% !"
输出图
输入 1 值
1
否
是
是 否
3、详细设计：
、主函数。分别编写出对图的创建、输出、删除边，判断是否为连通图而执
行相应的 操作、通过在主程序中调用这些函数，来达到实验要求。
创建的为无向图 有向图 !
"#$ !
创建的为连通图 非连通图 !
"%# !
&'()&*+)!
,--&../0&*+#) !
,--&/0&*+) !
11
*.
连通图深度优先遍历2 !
,--/&.&.) !
连通图广度优先遍历2 !
1
调用 +,!
'
调用 +,
'
调用 -+,!
'
调用 -+,
'
结束
