课程设计(论文)-基于BFS算法的图的遍历设计与实现

沈阳理工大学课程设计专用纸PAGEPAGEII0摘要本文采用图的邻接矩阵实现了最短路径问题中图的存储；采用队列实现了图的广度优先搜索（BFS），用类的成员函数实现了其各个功能。本C++程序实现了图的最短路径存储及BFS遍历，采用Visual

C++

6.0的控制台工程和MFC工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的广度遍历程序，通过对两种程序的测试结果表明：基于BFS算法的图的遍历算法原理正确，两种程序均能正确求解给定的图的遍历问题。关键词:邻接矩阵；队列；广度优先搜索；控制台工程；MFC图形界面

目录1 需求分析 12 算法基本原理 12.1邻接矩阵 12.2图的遍历——广度优先搜索(BFS） 23 类设计 33.1类的概述 33.2类的接口设计 43.3类的实现 54 基于控制台的应用程序 94.1主函数设计 94.2运行结果及分析 105 基于MFC的应用程序 125.1图形界面设计 125.2程序代码设计 145.3运行结果及分析 20结论 22参考文献 23PAGEPAGE23需求分析(1)图的应用和研究可追溯到18世纪。1736年，被称为图论之父的欧拉解决了哥尼斯堡（Konigsberg）问题，从而奠定了图论这门学科及其应用的基础。(2)图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。(3)程序测试数据来自姜学军李筠主编的《数据结构（C语言描述）》中，所选的无向图是:1132326657457488图1算法基本原理2.1邻接矩阵邻接矩阵是表示节点之间的相邻接关系的矩阵。若G是有n个节点的图，则G的邻接矩阵是如下定义的nXn矩阵。如图所示图G的邻接矩阵如下：21210111101001111010110110104343图GG的邻接矩阵2.2图的遍历——广度优先搜索(BFS）例如，有如下无向图：1132326657457488操作步骤如下：=1\*GB3①先输出1（1为起点）,将1入队；=2\*GB3②1出队，由于1的邻接顶点2和3未被访问过，输出2和3并将2和3入队；=3\*GB3③2出队,2的邻接顶点1;=4\*GB3④3出队，由于3的邻接顶点1被访问过，而邻接顶点6和7未被访问过，输出6和7并将6和7入队；=5\*GB3⑤4出队，由于4的邻接顶点2被访问过，而邻接顶点8未被访问过，输出8并将8入队；=6\*GB3⑥最后5，6，7，8出队，由于它们的邻接顶点都被访问过；此时队空，表示搜索已结束。类设计3.1类的概述本题设计的关键是对图的广度优先搜索算法的设计，由于使用邻接矩阵来存储图，就要将广度优先搜索的算法扩展到矩阵中。首先应设计无向图类Graph然后设计成员变量，用二维数组edge来表示图边的权值，一维数组vertex来表示顶点信息，eNum来表示边的数量，vNum来表示顶点数量，以及在遍历中需要的访问标记数组visited。最后还要设计成员函数实现对邻接矩阵的输出print()，广度优先搜索函数BFS()。考虑到图的初始化比较复杂，需要Graph(inta,intb)输入各个顶点信息，intInitGraph()输入每条边的权值。由于调用BFS()需要用到队列，还需要设计结点类QueueNode和队列类LinkQueue；用data表示结点数据，*next表示结点指针域，使用构造函数QueueNode()对结点进行初始化;用*front和*rear表示队列的前驱和后继，使用voidInit_Queue()对队列进行初审，判断队列是否为空:voidInit_Queue(),入队类操作:intEn_Queue(DataTypee),出队列操作:voidDe_Queue(DataType&e)。由于程序比较复杂，Graph类的接口实现放在Graph.h中,QueueNode类和LinkQueue类的接口放在Queue.h中，类的实现和主函数放在main.cpp中。3.2类的接口设计**************************************************************************************//Graph.hGraph类的接口设计usingnamespacestd;constintmaxnum=100; //设置邻接矩阵的最大阶数classGraph{private: charvertex[maxnum];//图的顶点信息 intedge[maxnum][maxnum]; //图的边信息 intvNum; //顶点个数 inteNum; //边的个数 boolvisited[maxnum]; //标记这个顶点是否被访问过,0表示没有,1表示已经被访问过public: Graph(inta,intb); //构造函数 intInitGraph(); //图类的初始化函数 voidprint(); //输出邻接矩阵 voidBFS(); //广度优先遍历邻接矩阵};**************************************************************************************//Queue.hQueueNode类和LinkQueue类的接口设计：typedefintDataType;classQueueNode{public: DataTypedata; QueueNode*next; QueueNode() { next=NULL; }};classLinkQueue{public: QueueNode*front; QueueNode*rear; LinkQueue(){}; //构造函数 voidInit_Queue() //初始化 { front=NULL; rear=NULL; } ~LinkQueue() //析构函数 { QueueNode*p,*q; p=front; while(p) { q=p; p=p->next; deleteq; } front=NULL; rear=NULL; } intEmpty_Queue(); //判断队列是否为空 intEn_Queue(DataTypee); //入队列操作 voidDe_Queue(DataType&e); //出队列操作};3.3类的实现//main.cppintLinkQueue::Empty_Queue(){ return(front==NULL&&rear==NULL);}intLinkQueue::En_Queue(DataTypee){ QueueNode*p=newQueueNode; if(p)//判断是否申请成功 { p->data=e; if(rear)rear->next=p; elsefront=rear=p; return1; } else return0;}voidLinkQueue::De_Queue(DataType&e){ QueueNode*p; if(!Empty_Queue()) { p=front; e=p->data; front=front->next; if(!front)rear=NULL; deletep; }}Graph::Graph(inta,intb){ cout<<"创建顶点数为"<<a<<"边数"<<b<<"的无向图"<<endl; vNum=a; eNum=b;//为了防止原先存在e[][]中的数据对今后的搜索造成影响,所以对其进行初始化 for(inti=0;i<vNum;i++) { for(intj=0;j<vNum;j++) { edge[i][j]=0; } }}intGraph::InitGraph(){ inti,j,temp,flag=0; for(i=0;i<vNum;i++) { cout<<"请输入第"<<i+1<<"个顶点信息:"; cin>>vertex[i]; } //输入各个边的具体情况 cout<<"请输入各个边的权值"<<endl; for(i=0;i<vNum;i++) { for(j=i+1;j<vNum;j++) { cout<<vertex[i]<<"->"<<vertex[j]<<"：";cin>>temp; edge[i][j]=temp; edge[j][i]=temp; if(temp)flag++; if(flag==eNum) { cout<<"初始化无向图邻接矩阵完毕"<<endl; return0; } } } return1;}//输出邻接矩阵voidGraph::print(){ cout<<"邻接矩阵为"<<endl; inti,j; for(i=0;i<vNum;i++) { for(j=0;j<vNum;j++) cout<<edge[i][j]<<""; cout<<endl; }}voidGraph::BFS(){ cout<<"广度优先搜索（BFS）"<<endl; inti,j; LinkQueueQ; //生成辅助队列对象Q for(i=0;i<vNum;++i) visited[i]=false; //访问标志数组初始化 Q.Init_Queue(); //初始化队列Q for(i=0;i<vNum;++i) if(!visited[i]) //对未访问的顶点进行收缩 { visited[i]=true; cout<<vertex[i]<<""; Q.En_Queue(i); while(!Q.Empty_Queue()) //队列非空 { intm; Q.De_Queue(m); for(j=0;j<vNum;j++) if((edge[m][j]==1)&&(!visited[j])) { visited[j]=true; cout<<vertex[j]<<""; Q.En_Queue(j); } } }}基于控制台的应用程序4.1主函数设计intmain(){ intx,y; cout<<"请输入顶点数x=";cin>>x; y=x*(x-1)/2; GraphG(x,y); G.InitGraph(); G.print(); G.BFS(); cout<<endl; return0;}4.2运行结果分析图1程序运行结果程序运行后首先创建了图类的对象，调用构造函数，产生一个顶点数为6，边数为15的无向图，然后初始化这个图，从键盘输入每个顶点的信息（a

b

c

d

ef）和每条边的权值。在主函数中直接调用邻接矩阵输出函数和广度优先搜索结果。基于MFC的应用程序MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成。5.1图形界面设计首先在VC中建立MFCAppWizard（exe）工程，名称为课程设计MFC，并在向导的Step1中选择Dialogbased，即建立基于对话框的应用程序，如图2~3所示。其余Steps均为默认选项。图2建立MFCAppWizard（exe）工程图3建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如图4所示界面图4图4所示的界面中包含了11个StaticText控件，4个Button控件，和12个EditBox控件，控件的基本信息列表如下表1所示。表1控件基本信息控件类别控件ID控件Caption说明StaticTextIDC_STATIC5顶点无向图各边的权值a->ba->ca->da->eb->cb->db->ec->dc->ed->eBottonIDC_BUTTON_LJ邻接矩阵IDC_BUTTON_BFS广度优先遍历IDC_BUTTON_CLEAN清空IDCANCEL退出EditBoxIDC_EDIT_12邻接矩阵的权值IDC_EDIT_13IDC_EDIT_14IDC_EDIT_15IDC_EDIT_23IDC_EDIT_24IDC_EDIT_25IDC_EDIT_34IDC_EDIT_35IDC_EDIT_45IDC_EDIT_MATRIX显示邻接矩阵IDC_EDIT_COUT显示遍历结果5.2程序代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为12个EditBox控件建立MemberVariables，按Ctrl+w键进入MFCClassWizard界面，选择MemberVariables选项卡，可显示成员变量设置界面，如图5所示。图5成员变量设置界面下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。(1).将基于控制台应用程序的头文件Queue.h、Graph.h加入到MFC工程的头文件中，同时将控制台应用程序的源文件main.cpp改名为premain.h加入到MFC的头文件中，同时需要修改部分：a.删除main.cpp(premain.h)的主函数intmain()。b.删除main.cpp(premain.h)的删除print()函数。c.把Graph.h中的Graph类的所有成员该为public。d.在Graph.h中的Graph类声明一个Cstring型变量Dstr。e.在BFS()函数中CString型变量temp。f.将BFS()函数中的cout语句删除，同时将BFS()函数的部分代码修改： 在删除cout语句的地方加上temp.Format("%d",i+1);Dstr+=temp;两条语句。(2).在对话框类的实现文件课程设计MFCDlg.cpp加入#include"premain.h"(在premain.h中已经包含了”Queue.h”、”Graph.h”)，以实现在该文件中可使用Graph类。(3).在对话框类的实现文件课程设计MFCDlg.cpp中加入Graphg(5,6);,构造一个5顶点的无向图。(4).如图所示：示意图双击邻接矩阵按钮、广度优先搜索按钮、清空按钮，分别为其建立响应函数：邻接矩阵的响应函数OnButtonLj()；广度优先搜索的响应函数OnButtonBfs()；清空的响应函数OnButtonClean()(5).邻接矩阵的响应函数代码（OnButtonLj()）：voidCMFCDlg::OnButtonLj(){ CStringstr[10][10]; UpdateData(TRUE); g.edge[0][1]=m_e12;g.edge[1][0]=m_e12; g.edge[0][2]=m_e13;g.edge[2][0]=m_e13; g.edge[0][3]=m_e14;g.edge[3][0]=m_e14; g.edge[0][4]=m_e15;g.edge[4][0]=m_e15; g.edge[1][2]=m_e23;g.edge[2][1]=m_e23; g.edge[1][3]=m_e24;g.edge[3][1]=m_e24; g.edge[1][4]=m_e25;g.edge[4][1]=m_e25; g.edge[2][3]=m_e34;g.edge[3][2]=m_e34; g.edge[2][4]=m_e35;g.edge[4][2]=m_e35; g.edge[3][4]=m_e45;g.edge[4][3]=m_e45; m_str_matrix=""; UpdateData(0); for(inti=0;i<5;i++) { for(intj=0;j<5;j++) { str[i][j].Format("%i,",g.edge[i][j]); m_str_matrix+=str[i][j]; } m_str_matrix+="\r\n"; UpdateData(FALSE); } UpdateData(FALSE);}(6).广度优先搜索的响应函数代码（OnButtonBfs()）：voidCMFCDlg::OnButtonBfs(){ //TODO:Addyourcontrolnotificationhandlercodehere intx; CStringstr[10][10]; UpdateData(TRUE); g.edge[0][1]=m_e12;g.edge[1][0]=m_e12; g.edge[0][2]=m_e13;g.edge[2][0]=m_e13; g.edge[0][3]=m_e14;g.edge[3][0]=m_e14; g.edge[0][4]=m_e15;g.edge[4][0]=m_e15; g.edge[1][2]=m_e23;g.edge[2][1]=m_e23; g.edge[1][3]=m_e24;g.edge[3][1]=m_e24; g.edge[1][4]=m_e25;g.edge[4][1]=m_e25; g.edge[2][3]=m_e34;g.edge[3][2]=m_e34; g.edge[2][4]=m_e35;g.edge[4][2]=m_e35; g.edge[3][4]=m_e45;g.edge[4][3]=m_e45; g.Dstr=""; g.BFS(); m_str_cout=""; UpdateData(FALSE); for(x=0;x<5;x++) m_str_cout+=g.Dstr.GetAt(2*x)+'0'; m_str_cout.MakeUpper(); UpdateData(FALSE);}(7).清空的响应函数代码（OnButtonClean()）voidCMFCDlg::OnButtonClean(){ //TODO:Addyourcontrolnotificationhandlercodehere UpdateData(TRUE); m_e12=0; m_e13=0; m_e14=0; m_e15=0; m_e23=0; m_e24=0; m_e25=0; m_e34=0; m_e35=0; m_e45=0; m_str_matrix=""; m_str_cout=""; UpdateData(FALSE);}5.3运行结果及分析运行程序后，首先出现的界面如图6所示。图6程序初始运行界面分别输入a->b、a->c、a->c、a->d、a->e、b->c、b->d、b->e、c->d、c->e、d->e，单击邻接矩阵按钮后，可将此无向图的邻接矩阵表示出现对话框中，如图7所示。图7点击邻接矩阵按钮后的界面单击广度优先遍历按钮，实现图的邻接矩阵按照广度优先搜索遍历并显示遍历结果，如图8所示。图8单击广度优先遍历按钮后的界面单击清空按钮后，对话框的编辑框内容全部置零，如图9所示。图8单击清空按钮后的界面单击退出按钮后，程序能够正常实现退出。

结论本次课程设计作为编写Windows程序的初步尝试，能够实现程序的主要功能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标，本此编写的MFC程序虽然能实现所需功能，但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足，程序员可以此为例多加实践，达到能熟练掌握的效果。MFC为Windows应用程序开发者提供了一种快速开发的工具，尤其是MFC中提供的多种标准控件，使得开发者不再将过多的心思花在界面代码编写上，而将更多的精力投入到应用程序的逻辑功能上，在很大程度上减轻了程序员的负担。由于MFC是通用框架，没有很好的针对性，当然也就丧失了一些灵活性和效率，但是MFC的封装很浅，所以在效率上损失不大，灵活性也很好，虽然也有很多缺陷，但还是一个比较好的编程环境。此次课程设计让我体会到了真正的结合C++图形界面开发，同样也有C++面向对象程序设计的特点，这样编出来的程序也利于我们更加深入了解C++的编程。虽然程序可以成功的编译运行，但是仍然有很多的缺点和不足：1.graph类的设计有悖于数据结构存储的方式，并且类的成员函数全部为public，不利于信息的安全，应该将他们归于private，再设计一个成员函数对其赋值。2.程序的界面设计并不完美，只能输入5个顶点的无向图图，应该设计为动态的输入界面，满足用户的不同需求。3.主程序没有设计输入顶点信息的函数，所以在广度优先遍历的时候不能输出顶点信息。通过此次任务式的程序设计，不仅巩固了我们在课堂所学的知识。更重要的是学会了沟通和交流。感觉课堂上的知识应用到实际中还是很欠缺的，因此大学里的学习课外自主学习是很重要的。获取资料以完成任务的任务型学习是很有必要的。感觉自己在面向对象的方面还很欠缺，特别是MFC方面，还有就是C++较难学。我相信自己努力了就会有回报的。凡是认真去学，都可以做好的，需要自己戒骄戒躁。真正静下心来。在IT的世界里，需要不断学习，不断努力。参考文献谭浩强．C++基础入门大全．北京：清华大学出版社，2012:100-102郑莉，董渊，张瑞丰．C++语言程序设计（第3版）．北京：清华大学出版社，2007:25-60钱能．C++程序设计教程（第2版）．北京：清华大学出版社，2007:100-130RichardC.Leinecker,TomArcher.VisualC++6宝典.张艳,张谦译.北京:电子工业出版社,1999李强,贾云霞.VisualC++项目开发实践.北京:中国铁道出版社,2004郑莉,董渊,张瑞丰.C++语言程序设计.2003H.M.Deitel,P.J.Deitel.SmallC++HowtoProgram.2006基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统基于51单片机的嵌入式Internet系统的设计与实现单片机监测系统在挤压机上的应用HYPERLINK"/