c 基于dfs算法的图的遍历问题求解课程设计

《c 基于dfs算法的图的遍历问题求解课程设计 》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C++课程设计(论文)成绩评定表学生姓名xxx班级学号xxx专业通信工程课程设计题目基于DFS算法的图的遍历问题求解评语组长签字：成绩日期20年月日课程设计任务书学院信息科学与工程专业通信工程学生姓名xxx班级学号xxx课程设计题目基于DFS算法的图的遍历问题求解实践教学要求与任务图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。进行类的设计与实现，解决图的遍历问题。具体要求如下：（1）采用图的邻接矩阵或邻接表实现最短路径问

2、题中图的存储；（2）采用递归程序实现图的深度优先搜索（DFS）；（3）将上述功能作为类的成员函数实现，编写主函数测试上述功能。工作计划与进度安排第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要本文采用图的邻接矩阵实现了最短路径问题中图的存储；采用递归程序实现了图的深度优先搜索（DFS），用类的成员函数实现了其各个功能。类是所有C++语言的一大特征，是实现本程序设计的基础

3、。图是一种比较复杂的非线性数据结构，深度优先搜索（DFS）是图的遍历的方法之一，它是指按照深度方向实现图的每个结点的搜索，类似于树的先根遍历访问了图的每一个结点，而采用邻接矩阵可以实现图的最短路径存储，提高程序的优越性。本C++程序实现了图的最短路径存储及ＤＦＳ遍历，采用VisualC++6.0的控制台工程和MFC工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的深度遍历程序，通过对两种程序的测试结果表明：基于ＤＦＳ算法的图的遍历算法原理正确，两种程序均能正确求解给定的图的遍历问题。关键词：邻接矩阵，类的成员函数，递归调用，深度优先搜索，控制台工

4、程，ＭＦＣ图形界面。目录1、需求分析12、算法基本原理13、类设计34、基于控制台的应用程序34.1类的接口设计34.2类的成员函数设计44.3主函数设计65、基于控制台的应用程序设计65.1程序运行结果65.2运行结果分析76、基于MFC的图形界面程序开发76.1基于MFC的图形界面程序设计86.2程序测试13结论14参考文献151、需求分析（1）图作为一种非线性数据结构，被广泛应用与多个技术领域本设计依靠类的成员函数完成以下功能：采用图的邻接矩阵实现最短路径问题中图的存储；采用递归程序实现图的深度优先搜索（DFS）。采用VisualC++6.0

5、的控制台工程和MFC工程分别实现邻接矩阵在桌面上的的显示以及实现对图的深度遍历程序。（2）程序测试数据来自姜学军、李筠主编的《数据结构（C语言描述）》中，所选的无向图是:132657482、算法基本原理(1)邻接矩阵是表示节点之间的相邻接关系的矩阵。若G是有n个节点的图，则G的邻接矩阵是如下定义的nXn矩阵。如图所示图G的邻接矩阵如下：21011110101101101043图GG的邻接矩阵第15页共21页(1)图的遍历——深度优先搜索例如，有如下无向图：13265748操作步骤如下：①先输出1（1为起点）；②将1的邻接顶点2和3压入栈中；③弹出栈

6、顶元素2，由于2未被访问过，输出2，然后将2的邻接顶点4和5压栈；④弹出栈顶元素4，由于4未被访问过，输出4，然后将4的邻接顶点8和2压栈；⑤弹出2，由于2已经被访问过，故弹出8，由于8未被访问过，输出8，再将8的邻接顶点4、5、6、7压栈；⑥弹出4，由于4已经被访问过，故弹出5，由于5未被访问，输出5，然后将5的邻接顶点2和8压栈；⑦弹出已经访问过的2和8，再弹出6，由于6未被访问过，输出6，再将6的邻接顶点3和8压栈；⑧弹出3，由于3未被访问过，输出3，将3的邻接顶点1、6、7压栈；⑨弹出已经访问过的1和6，再弹出7，由于7未被访问过，输出7，

7、再将7的邻接顶点3和8压栈；⑩最后弹出都已经访问过的3、8、8、7、5、3；此时栈为空，表示搜索结束。第15页共21页3、类设计本题设计的关键，是对图的深度优先搜索算法的设计，由于使用邻接矩阵来存储图，就要将深度优先搜索的算法扩展到矩阵中。首先，应设计无向图类graph，然后设计成员变量，用二维数组e来表示图边的权值，二维数组v来表示顶点信息，eNum用来表示边的无数量，vNum用来表示顶点数量，以及在遍历中需要的访问标记数组visited。最后还要设计成员函数，实现对邻接矩阵的输出print()，深度优先搜索函数DFS()和递归调用dfs()。考

8、虑到图的初始化比较复杂，需要输入各个顶点信息，和每条边的权值，还要设计函数InitGraph()实现对数组的初始化。4、基