课程设计（论文）-基于DFS算法的图的遍历问题求解.docx

封皮（按学校要求手工填写）成绩评定表学生姓名郭佳晨班级学号1203060120专业通信工程课程设计题目基于dfs算法的图的遍历问题求解评语组长签字：成绩日期2014 年 1月 4日课程设计任务书学院信息科学与工程学院专业通信工程学生姓名郭佳晨学号1203060120设计题目基于dfs算法的图的遍历问题求解实践教学要求与任务:图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。进行类的设计与实现，解决图的遍历问题。具体要求如下：（1）采用图的邻接矩阵或邻接表实现最短路径问题中图的存储；（2）采用递归程序实现图的深度优先搜索（dfs）；（3）将上述功能作为类的成员函数实现，编写主函数测试上述功能。工作计划与进度安排:第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师（签字）：年月日学院院长（签字）年月日摘要深度优先搜索（depth-first-search）是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。目录1 需求分析- 3 -2 算法基本原理- 3 -3 类设计- 3 -4 详细设计- 3 -4.1 类的成员初步设计错误！未定义书签。4.2 类的成员函数设计错误！未定义书签。4.3 主函数设计错误！未定义书签。5 dos界面程序运行结果及分析- 3 -5.1 程序运行结果- 3 -5.2运行结果分析- 3 -6 基于mfc的图形界面程序开发- 3 -6.1 基于mfc的图形界面程序设计- 3 -6.2 程序测试- 3 -6.3 mfc程序编写总结错误！未定义书签。7 参考文献- 3 -1 需求分析(1)图的应用和研究可追溯到18世纪。1736年，被称为图论之父的欧拉解决了哥尼斯堡（konigsberg）问题，从而奠定了图论这门学科及其应用的基础。(2)图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。(3)程序测试数据来自姜学军李筠主编的数据结构（c语言描述）中，所选的无向图是:132657482 算法基本原理(1) 邻接矩阵是表示节点之间的相邻接关系的矩阵。若g是有n个节点的图，则g的邻接矩阵是如下定义的n x n矩阵。如图所示图g的邻接矩阵如下：210 1 1 11 0 1 01 1 0 11 0 1 043图gg的邻接矩阵(2) 图的遍历深度优先搜索例如，有如下无向图：13265748操作步骤如下：先输出1（1为起点）；将1的邻接顶点2和3压入栈中；弹出栈顶元素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的邻接顶点3和8压栈；最后弹出都已经访问过的3、8、8、7、5、3；此时栈为空，表示搜索结束。3 类设计本题设计的关键是对图的深度优先搜索算法的设计，由于使用邻接矩阵来存储图，就要将深度优先搜索的算法扩展到矩阵中。首先应设计无向图类graph，然后设计成员变量，用二维数组e来表示图边的权值，二维数组v来表示顶点信息，enum来表示边的无数量，vnum来表示顶点数量，以及在遍历中需要的访问标记数组visited。最后还要设计成员函数实现对邻接矩阵的输出print()，深度优先搜索函数dfs()和递归调用dfs()。考虑到图的初始化比较复杂，需要输入各个顶点信息，和每条边的权值，还要设计函数initgraph()实现对数组的初始化。4 详细设计由于类的设计较为简单，将类和主函数放在同一个文件中，方便调试，首先声明无向图类graph，进行类的设计，然后设计主函数，直接在主函数中实现类，并输出邻接矩阵和深度优先搜索结果。#include#include using namespace std;constintmaxnum = 100; class graphpublic:char vmaxnum; int emaxnummaxnum;intvnum; intenum; int visitedmaxnum; graph(inta,int b); intinitgraph(); void print(); void dfs(int i); void dfs(); ; graph :graph(inta,int b) cout创建顶点数为a边数b的无向图endl; vnum=a;enum=b;for(int i=0;ivnum;i+) for(int j=0;jvnum;j+) eij = 0; int graph :initgraph()inti,j,temp,flag=0; for (i=0; ivnum; i+)cout请输入第i+1 vi;cout请输入各个边的权值endl;for (i=0; ivnum; i+)for(j=i+1;jvnum;j+)cout vi vjtemp;eij = temp; eji = temp; if(temp)flag+;if(flag=enum)cout初始化无向图邻接矩阵完毕endl;return 0;return 1;void graph : print()cout邻接矩阵为endl;inti,j;for (i=0; ivnum; i+)for (j=0;jvnum; j+)cout eij ;coutendl;void graph : dfs(int i) coutvi; visitedi = 1; for(int j=0;jvnum;j+) if( eij!=0 & visitedj=0) dfs(j); void graph : dfs() int i; for(i=0;ivnum;i+) visitedi = 0; for(i=0;ivnum;i+) if(visitedi=0)dfs(i);coutendl; int main() graph g(5,6); g.initgraph(); g.print();cout深度优先搜索的结果:endl; g.dfs(); return 0; 5 dos界面程序运行结果及分析5.1 程序运行结果程序运行结果如图2所示。图2 程序运行结果5.2运行结果分析程序运行后首先创建了图类的对象，调用构造函数，产生一个顶点数为5，边数为6的无向图，然后初始化这个图，输入每个顶点的信息和每条边的权值。在主函数中直接调用邻接矩阵输出函数和深度优先搜索结果。6 基于mfc的图形界面程序开发mfc的图形界面程序设计可在上述类设计的基础上进行改造，mfc的图形界面程序与dos界面程序的主要不同点是：mfc图形界面程序与dos界面程序的输入输出方式不同，dos界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等i/o流实现，而mfc的图形程序界面采用标准windows窗口和控件实现输入输出，因此必须在mfc类的框架下加入上面所设计的图类，并通过图形界面的输入输出改造来完成。6.1 基于mfc的图形界面程序设计（1）界面设计首先在vc中建立mfc appwizard(exe)工程，名称为dfs，并在向导的step1中选择dialog based，即建立基于对话框的应用程序，如下图45所示。图4 建立mfc appwizard(exe)工程图5 建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图6所示。图6 方程组求解程序界面设计图6所示的界面中包含了1个static text控件，3个button控件，和12个edit box控件，控件的基本信息列表如下表1所示。表1 控件基本信息控件类别控件id控件caption说明static textidc_static5顶点6条边无向图bottonidc_button_lj邻接矩阵idc_button_sd深度优先遍历idc_button_exit退出edit boxidc_edit_12 idc_edit_15邻接矩阵的权值idc_edit_23 idc_edit_25idc_edit_34 idc_edit_35idc_edit_45（2）代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为12个edit box控件建立member variables，按ctrl+w键进入mfc classwizard界面，选择member variables选项卡，可显示成员变量设置界面，如图7所示。图7 成员变量设置界面通过该界面设置与24个edit box控件对应的成员变量，具体如表2所示。表2 控件基本信息控件id成员变量类型成员变量名称idc_edit_12 idc_edit_45intm_e12m_e45idc_edit_ljcstringm_ljidc_edit_sdcstringm_sd下面是编写代码的重要阶段，可以借鉴在设计基于dos界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。 将dfs.cpp文件重新命名为dfs.h，并将其加入mfc工程。 修改dfs.h文件具体包括：l 将显示矩阵print()函数注释掉，在图形界面的程序上已经不需要个函数承担输出功能了；l 将主函数注释掉，已经不需要主函数进行操作了；l 将深度优先搜索函数dfs()和dfs()的cout语句去掉，不需要也不能够使用cout流实现输出；l 将graph类的所有成员改为公共的，方便给graph类的成员变量赋值l 在graph类中声明一个cstring型的变量dstr，用来保存函数输出结果的字符串；l 在函数dfs内声明一个cstring型变量temp，用来临时存储函数输出的结果，并添加以下语句temp.format(%d,i+1)；dstr+=temp； 在对话框类的实现文件cdfs_mfcdlg.cpp中加入#include dfs.h，以实现在该文件中可使用graph类。 在对话框类的实现文件cdfs_mfcdlg.cpp中加入graph g(5,6);,构造一个5顶点的无向图； 编写邻接矩阵按钮的消息处理函数，实现图的邻接矩阵在界面上的显示，具体代码如下：voidcdfs_mfcdlg:onbuttonlj() / todo: add your control notification handler code herecstringstr1010;updatedata();g.e01=m_e12;g.e10=m_e12;g.e02=m_e13;g.e20=m_e13;g.e03=m_e14;g.e30=m_e14;g.e04=m_e15;g.e40=m_e15;g.e12=m_e23;g.e21=m_e23;g.e13=m_e24;g.e31=m_e24;g.e14=m_e25;g.e41=m_e25;g.e23=m_e34;g.e32=m_e34;g.e24=m_e35;g.e42=m_e35;g.e34=m_e45;g.e43=m_e45;m_lj=;updatedata(0);for (int i=0;i5;i+)for (int j=0;j5;j+)strij.format(%i,g.eij);m_lj+=strij;m_lj+=rn;updatedata(0); 编写深度优先遍历按钮的消息处理函数，实现对图的深度遍历，并显示到界面上，具体代码如下：voidcdfs_mfcdlg:onbuttonsd() / todo: add your control notification handler code herecstringstr1010;updatedata();g.e01=m_e12;g.e10=m_e12;g.e02=m_e13;g.e20=m_e13;g.e03=m_e14;g.e30=m_e14;g.e04=m_e15;g.e40=m_e15;g.e12=m_e23;g.e21=m_e23;g.e13=m_e24;g.e31=m_e24;g.e14=m_e25;g.e41=m_e25;g.e23=m_e34;g.e32=m_e34;g.e24=m_e35;g.e42=m_e35;g.e34=m_e45;g.e43=m_e45;g.dstr=;g.dfs();m_sd=;updatedata(0);m_sd=g.dstr;updatedata(0);退出按钮代码如下：voidcguasslineguidlg:onbuttonexit() / todo: add your control notification handler code hereonok();6.2程序测试运行程序后，首先出现的界面如图8所示。图8程序初始运行界面在编辑框输入邻接矩阵的权值后，单击邻接矩阵按钮，可将这个5顶点的无向图邻接矩阵在界面上显示出来，如图9所示。图9读入数据后的界面单击深度优先遍历按钮，实现对图的深度优先搜索并显示出搜索结果，如图10所示。图10求解方程组后的界面单击退出按钮后，程序能够正常实现退出。7结论mfc为windows应用程序开发者提供了一种快速开发的工具，尤其是mf