图的遍历和生成树求解说明书

*******************

实践教学

*******************

兰州理工大学

计算机与通信学院

2012年春季学期

\\数据结构课程设计

题 目：图的遍历和生成树求解实现 专业班级：信息与计算科学（1）班 姓 名：

杨猛 学 号： 10500125 指导教师： 张永 成 绩：

目 录

摘 要 .......................................................................................... 2 关键字 .......................................................................................... 2 序 言 .......................................................................................... 2 正 文 .......................................................................................... 3 1．采用类C语言定义相关数据类型 ...................................... 3 2．各模块流程图及伪码算法 ................................................... 3 3．函数的调用关系图 ............................................................. 10 4．调试分析 ............................................................................. 11

A.调试中遇到的问题及对问题的解决方法 ......................... 11 B.算法的时间复杂度和空间复杂度 ..................................... 11

5．测试结果 ............................................................................. 11 设计总结 .................................................................................... 18 参考文献 .................................................................................... 19 致 谢 .......................................................................................... 19 附录：源程序 ........................................................................... 20

1

摘 要

很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。

关键字：

图、深度优先遍历、广度优先遍历、生成树。

序 言

计算机科学与技术本科专业《算法与数据结构课程设计》是在《算法与数据结构》课程结束之后，要求学生能够设计程序，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养自己的动手能力，独立思考能力，发现问题并解决问题能力而开设的课程。

从课程性质上讲，《算法与数据结构课程设计》是一门技术实践课。其要求是：学会分析研究计算机加工的数据结构的特点，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，在前期学习过程中对复杂程序设计理解掌握基础上做进一步的实践训练，并且能编写出结构清楚，正确易读，符合软件工程规范的程序。

很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。

由于此题目需要较多的数据输入，同时功能模块也比较的多，故在命令提示符下采用了图形化菜单式的界面，使得选择功能和输入数据都比较容易。

2

正 文

1．采用类C语言定义相关数据类型

图存储结构的定义：

1）顺序存储（邻接矩阵）

#define MAX_VERTEX_NUM 30 //最大顶点个数 Typedef enum{DG,DN,UDG,UDN} GraphKind; //图的种类：有向图、有向网、无向图、无向网

ArcTypeAdjMtrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //ArcType是顶点关系类型，对无权图，用0和1表示是否相邻，对于网，则为权值类型

typedef struct {

VertexType vex[MAX_VERTEX_NUM]; //顶点数组 AdjMtrix arc; //邻接矩阵

int vexnum,arcnum; //图中的顶点数和边数 GraphKind kind; //图的种类 }GraphMtrix; （2）邻接表的存储

#define MAX_VERTEX_NUM 30 //最大顶点个数 typedef struct EdgeNode{ //表结点 int adjvex; //边或弧依赖的顶点序号

InfType *info; //弧或边的相关信息，在网中则为权值 struct EdgeNode *next; }EdgeNode;

typedef struct VexNode{ //顶点元素 VertexType vextex; EdgeNode *link;

}VexNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ //邻接表 AdjList vertices;

int vexnum,arcnum; //图中的顶点数和边数 GraphKind kind; //图的种类 } AdjListGrap

2．各模块流程图及伪码算法

(1) 遍历算法

a.深度优先遍历

3