《数据结构》课程设计报告

一 设计题目

   编制一个图及其操作的程序

二 需求分析

   本程序在VC++环境下编写，实现图的广度，深度优先遍历，并输出结果。

   （1）输入的形式：输入顶点的标号和元素；输入每条边依附的顶点和权值；输入的权值均置为1。元素个数小于20个。

   （2）输出的形式：输出时显示输入的顶点标号和元素；输入弧依附的顶点和权值；输出广度优先遍历及结果，深度优先遍历及结果。程序结束。

   （3）程序所能表达的功能：ａ对任意给定的图（顶点数和边数自定），建立它的邻接表ｂ实现图的广度优先遍历和深度优先遍历，并输出结果。

三 方案设计

   （1）为了实现上述程序功能，需要定义图的抽象数据类型：

        ADT Graph{

            数据对象V：是具有相同特性的数据元素的集合，称为顶点集。

数据关系R： R={V}

            VR={<v,w>}

基本操作：

           CreatGraph(&G,V,VR);

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

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

           LocateVex(G,u);

                初始条件：图G存在，u和G中顶点有相同特征。

                操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其他信息。

           FirstAdjVex(G,V,w);

                初始条件：图G存在，V是G中某个顶点。

                操作结果：返回V的第一个邻接点。若顶点在G中没有邻接点，则返回“空”。

NextAdjVex(G,V,w);

初始条件：图G存在，V是G中某个顶点,w是V的邻接顶点。

操作结果：返回ｖ的下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”

DFSTraverse（G，Visit（））；

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次，一旦Visit()失败，则操作失败。

BFSTraverse(G,Visit());

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次，一旦Visit()失败，则操作失败。

}ADT Graph.

(2)在进行广度优先遍历程序时，采用了循环队列的存储方式进行存储。

（3）本程序包含9个函数：   

 ①主函数main()

     ②创建无向网CreatUDN()

     ③深度优先遍历DFS()

     ④广度优先遍历BFS()

     ⑤构建空队列InitQueue()

     ⑥插入队尾元素EnQueue()

     ⑦删除对头元素DeQueue()

     ⑧访问K的第一个邻接顶点FirstVex()

     ⑨访问顶点i的第j个邻接顶点的下一个邻接顶点NextVex()

各函数间关系如下:

四 程序框图

   （1）深度优先遍历（DFS）的过程：类似于树的先根遍历.从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

此深度优先遍历采用了递归的过程。

       （2）广度优先遍历(BFS)的过程：类似于树的按层次遍历的过程。是以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1、2 ...的顶点。

        设计广度优先遍历的程序流程图

五 程序代码(见附加页)

六 程序调试过程（略）

七 测试结果

       输出结果为

       输入顶点数和弧数：8 9

       输入8个顶点

       输入顶点0：a

 输入顶点1：b

   输入顶点2: c

   输入顶点3: d

   输入顶点4: e

   输入顶点5: f

   输入顶点6: g

   输入顶点7：h

   输入9条弧

   输入弧0：a b 1

   输入弧1：b d 1

   输入弧2：b e 1

   输入弧3：d h 1

   输入弧4：e h 1

   输入弧5：a c 1

   输入弧6：c f 1

   输入弧7：c g 1

   输入弧8：f g 1

广度优先遍历：a b d h e c f g

深度优先遍历：a b c d e f g h

程序结束

----------------------------------------