内蒙古科技大学。
本科生课程设计**。
题目：图的遍历。
2024年07月05日。
内蒙古科技大学课程设计任务书。
目录。第一章图的遍历原理 3
1.1 总述 3
1.2 深度优先遍历 3
1.3 广度优先遍历 4
第二章需求分析 4
第三章总体设计 5
3.1程序设计思路 5
3.2 功能视图 5
第四章类的设计 6
4.1 graphudn类的设计 6
4.2 queue类的设计 7
第五章详细设计 8
5.1 工程视图和类视图 8
5.2 主要算法的流程图 9
5.2.1 主函数的流程图 9
5.2.2 深搜流程图 10
5.2.3 广搜流程图 11
第六章测试 13
6.1 菜单界面 13
6.2 创建无向网 13
6.3 输出图 14
6.4 输出顶点v的第一个邻接点 15
6.5 输出顶点v的下一个邻接点 15
6.6 深搜 16
6.7 广搜 16
第七章总结 16
附录：程序** 18
参考文献 27
图的遍历：从图中某一顶点出发访遍图中其余顶点，且使得每一个顶点仅被访问一次。这一过程就叫做图的遍历。
深度优先遍历类似于树的先根遍历，是树的先根遍历的推广。
假如初始状态是图中所有顶点未曾被访问，则深度优先遍历可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到；若图中此时尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。
以图1.1为例，假如从顶点v1出发进行搜索，在访问了顶点v1之后，选择邻接点v2。因为v2未曾访问，则从v2出发进行搜索。
以此类推，接着从v4，v8，v5出发进行搜索。在访问了v5之后，由于v5的邻接点都已被访问，则搜索回到v8。由于同样的理由，搜索回到v4，v2直到v1，此时由于v1的另一个邻接点未被访问，则搜索又从v1到v3，再继续进行下去。
由此，得到的顶点访问序列为：
v1—v2—v4—v8—v5—v3—v6—v7
广度优先遍历类似于树的按层次遍历的过程。
假如从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若图中此时尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。
以图1.1为例，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成图的遍历。
得到的顶点访问序列为：
v1—v2—v3—v4—v5—v6—v7—v8
要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：
输入图、输出图。
求图中顶点v的第一个邻接点。
求图中顶点v的下一个邻接点。
深度优先遍历图。
广度优先遍历图。
并设计主函数测试该类（或类模板）。
本系统有六个基本功能：输入图，输出图，求图中顶点v的第一个邻接点，求图中顶点v的下一个邻接点，深度优先遍历图，广度优先遍历图。
输入图：首先需输入顶点数及边数，然后根据顶点数确定矩阵大小，再根据边数输入对应的两点及权值。
输出图：先输出有所有边及对应的权值，再输出矩阵。
求图中顶点v的第一个邻接点：通过输入顶点v就可以输出其第一个邻接点。
求图中顶点v的下一个邻接点：通过输入顶点v及另一点，就可以从该位置的下一个位置开始，找到顶点v的下一个邻接点。
深度优先遍历图：由1.1所述可知，图的深度优先遍历显然是一个递归的过程。
为了在遍历过程中便于区分顶点是否被访问过，需要附设一个访问标志数组，其初始值为false,一旦某个顶点被访问，则将其相应的分量置为true。
广度优先遍历图：由1.2所述可知，和深度优先遍历类似，在广度优先遍历的过程中也需要一个访问标志数组。
并且为了顺次访问路径长度为2，3，……的顶点，需要附设队列以存储已被访问的路径长度为1,2，……的顶点。
本程序主要包含六个功能，即图的创建，输出，访问顶点v的第一个和下一个邻接点，以及深搜和广搜。其功能视图如图2.1所示。
图3.1功能视图。
graphudn类包括：1.私有的数据成员，其中有顶点访问标志，顶点集，邻接矩阵，顶点数就边数 2.
公有的成员函数，其中有创建输出图，输出顶点v的第一个和下一个邻接点，以及深搜和广搜。具体见以下程序段：
classgraphudn
void add(intele入队。
int get出队。
boolisempty判断队列是否为空。
private:
intques[max_vertex_num];
本程序运行时的工程视图及类视图如图5.1,5.2所示。
图5.1 工程视图。
图5.2 类视图。
本程序的主函数中，首先定义及初始化所需变量，实例化对象，然后输出菜单界面供用户选择，通过switch函数实现选择功能，选择项目包括创建无向图，输出无向图，输出顶点v的第一个邻接点，输出顶点v的下一个邻接点，深搜，广搜以及退出。具体如图4.3所示。
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...