数据结构课程设计报告《图的遍历》(3)

一．设计任务：

我选课程设计是自选题目《图的遍历》。

要求：设计一个程序，实现图的广度，深度优先遍历。

二、设计时间

2009年12月28日

三、设计内容

1、需求分析

本题目需要解决的问题是将一幅已知图，对图进行遍历，并完成：

（1） 输出它的邻接矩阵；

（2） 根据人工选择进行深度优先搜索（Depth_First Search）和广度

优先搜索（Breadth_First Search），将搜索结果放入一队列中；

（3） 将队列中的搜索结果输出。

2、 概要设计：

(1)抽象数据的类型定义

数据对象：V是图具有相同特性的数据元素的集合，称为定顶点集 数据关系：R

R={VR}

VR={<v,w>/v,w∈v且p(v,w)}

基本操作：CreateGraph(&G,V,VR)

初始条件：V是图的顶点集，VR是图中弧的集合

操作结果：按V和VR的定义构造图G

基本操作：DFSTraverse(G,Visit())

BFSTraverse(G,Visit())

（2）主程序的流程以及各程序模块之间的调用关系：