基于BFS算法的图的遍历设计与实现

1、精选优质文档-倾情为你奉上0摘 要本文采用图的邻接矩阵实现了最短路径问题中图的存储；采用队列实现了图的广度优先搜索（BFS），用类的成员函数实现了其各个功能。本C+程序实现了图的最短路径存储及BFS遍历，采用Visual C+ 6.0的控制台工程和MFC工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的广度遍历程序，通过对两种程序的测试结果表明：基于BFS算法的图的遍历算法原理正确，两种程序均能正确求解给定的图的遍历问题。关键词:邻接矩阵；队列；广度优先搜索；控制台工程；MFC图形界面目 录专心-专注-专业1 需求分析(1)图的应用和研究可追溯到18世纪。1736年，被称

2、为图论之父的欧拉解决了哥尼斯堡（Konigsberg）问题，从而奠定了图论这门学科及其应用的基础。(2) 图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。(3)程序测试数据来自姜学军 李筠主编的数据结构（C语言描述）中，所选的无向图是:13265748图 1 2 算法基本原理2.1 邻接矩阵邻接矩阵是表示节点之间的相邻接关系的矩阵。若G是有n个节点的图，则G的邻接矩阵是如下定义的n X n矩阵。如图所示图G的邻接矩阵如下：210 1 1 11 0 1 01 1 0 1

3、1 0 1 043 图G G的邻接矩阵2.2 图的遍历广度优先搜索(BFS）例如，有如下无向图：13265748操作步骤如下：先输出1（1为起点）,将1入队；1出队，由于1的邻接顶点2和3未被访问过，输出2和3并将2和3入队；2出队,2的邻接顶点1;3出队，由于3的邻接顶点1被访问过，而邻接顶点6和7未被访问过，输出6和7并将6和7入队；4出队，由于4的邻接顶点2被访问过，而邻接顶点8未被访问过，输出8并将8入队；最后5，6，7，8出队，由于它们的邻接顶点都被访问过；此时队空，表示搜索已结束。3 类设计3.1 类的概述本题设计的关键是对图的广度优先搜索算法的设计，由于使用邻接矩阵来存储图，就要

4、将广度优先搜索的算法扩展到矩阵中。首先应设计无向图类Graph然后设计成员变量，用二维数组edge来表示图边的权值，一维数组vertex来表示顶点信息，eNum来表示边的数量，vNum来表示顶点数量，以及在遍历中需要的访问标记数组visited。最后还要设计成员函数实现对邻接矩阵的输出print()，广度优先搜索函数BFS()。考虑到图的初始化比较复杂，需要Graph(int a,int b)输入各个顶点信息，int InitGraph()输入每条边的权值。由于调用BFS()需要用到队列，还需要设计结点类QueueNode和队列类LinkQueue；用data表示结点数据，*next表示结点指

5、针域，使用构造函数QueueNode()对结点进行初始化;用*front和*rear表示队列的前驱和后继，使用void Init_Queue()对队列进行初审，判断队列是否为空: void Init_Queue(),入队类操作: int En_Queue(DataType e),出队列操作: void De_Queue(DataType &e)。由于程序比较复杂，Graph类的接口实现放在Graph.h中, QueueNode类和LinkQueue类的接口放在Queue.h中，类的实现和主函数放在main.cpp中。3.2类的接口设计*/Graph.hGraph类的接口设计using

6、namespace std; const int maxnum=100; /设置邻接矩阵的最大阶数 class Graph private: char vertexmaxnum; /图的顶点信息 int edgemaxnummaxnum; /图的边信息 int vNum; /顶点个数 int eNum; /边的个数 bool visitedmaxnum; /标记这个顶点是否被访问过,0表示没有,1表示已经被访问过 public: Graph(int a,int b); /构造函数 int InitGraph(); /图类的初始化函数 void print();/输出邻接矩阵 void BFS(

7、); /广度优先遍历邻接矩阵 ;*/Queue.hQueueNode类和LinkQueue类的接口设计：typedef int DataType;class QueueNodepublic:DataType data;QueueNode *next;QueueNode()next=NULL;class LinkQueuepublic:QueueNode *front;QueueNode *rear;LinkQueue();/构造函数void Init_Queue()/初始化front=NULL;rear=NULL;LinkQueue()/析构函数QueueNode *p,*q;p=front;

8、while(p)q=p;p=p->next;delete q;front=NULL;rear=NULL;int Empty_Queue();/判断队列是否为空int En_Queue(DataType e);/入队列操作void De_Queue(DataType &e);/出队列操作;3.3 类的实现/main.cppint LinkQueue:Empty_Queue() return(front=NULL&&rear=NULL);int LinkQueue:En_Queue(DataType e)QueueNode *p=new QueueNode;if(p)

9、 /判断是否申请成功p->data=e;if(rear)rear->next=p;else front=rear=p; return 1;elsereturn 0;void LinkQueue:De_Queue(DataType &e)QueueNode *p;if(!Empty_Queue()p=front;e=p->data;front=front->next;if(!front)rear=NULL;delete p;Graph:Graph(int a,int b) cout<<"创建顶点数为"<<a<<

10、;"边数"<<b<<"的无向图"<<endl; vNum=a; eNum=b; /为了防止原先存在e中的数据对今后的搜索造成影响,所以对其进行初始化 for(int i=0;i< vNum;i+) for(int j=0;j< vNum;j+) edgeij = 0; int Graph:InitGraph() int i,j,temp,flag=0; for (i=0;i<vNum;i+) cout<<"请输入第"<<i+1<<"个顶

11、点信息:" cin>>vertexi; /输入各个边的具体情况 cout<<"请输入各个边的权值"<<endl; for (i=0;i<vNum;i+) for(j=i+1;j<vNum;j+) cout<<vertexi<<"->"<<vertexj<<"：" cin>>temp; edgeij=temp; edgeji=temp; if(temp)flag+; if(flag=eNum) cout<&l

12、t;"初始化无向图邻接矩阵完毕"<<endl; return 0; return 1; /输出邻接矩阵 void Graph:print() cout<<"邻接矩阵为"<<endl; int i,j; for (i=0;i<vNum;i+) for (j=0;j<vNum;j+) cout<<edgeij<<" " cout<<endl; void Graph:BFS()cout<<"广度优先搜索（BFS）"<&l

13、t;endl;int i,j;LinkQueue Q;/生成辅助队列对象Qfor(i=0;i<vNum;+i)visitedi=false;/访问标志数组初始化Q.Init_Queue();/初始化队列Qfor(i=0;i<vNum;+i)if(!visitedi)/对未访问的顶点进行收缩visitedi=true;cout<<vertexi<<" "Q.En_Queue(i);while(!Q.Empty_Queue()/队列非空int m;Q.De_Queue(m);for(j=0;j<vNum;j+)if(edgemj=1)&

14、amp;&(!visitedj)visitedj=true;cout<<vertexj<<" "Q.En_Queue(j);4 基于控制台的应用程序4.1主函数设计int main() int x,y; cout<<"请输入顶点数x="cin>>x; y=x*(x-1)/2; Graph G(x,y); G.InitGraph(); G.print(); G.BFS(); cout<<endl; return 0; 4.2运行结果分析图1程序运行结果程序运行后首先创建了图类的对象，调用构

15、造函数，产生一个顶点数为6，边数为15的无向图，然后初始化这个图，从键盘输入每个顶点的信息（a b c d e f）和每条边的权值。在主函数中直接调用邻接矩阵输出函数和广度优先搜索结果。5 基于MFC的应用程序MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面

16、所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成。5.1 图形界面设计首先在VC中建立MFC AppWizard（exe）工程，名称为课程设计MFC，并在向导的Step1中选择Dialog based，即建立基于对话框的应用程序，如图23所示。其余Steps均为默认选项。图2 建立MFC AppWizard（exe）工程图3 建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如图4所示界面图4图4所示的界面中包含了11个Static Text控件，4个Button控件，和12个Edit Box控件，控件的基本信息列表如下表1所示。表1 控件基本信息控件类别控件ID控件

17、Caption说明Static TextIDC_STATIC5顶点无向图各边的权值a->ba->ca->da->eb->cb->db->ec->dc->ed->eBottonIDC_BUTTON_LJ邻接矩阵IDC_BUTTON_BFS广度优先遍历IDC_BUTTON_CLEAN清空IDCANCEL退出Edit BoxIDC_EDIT_12邻接矩阵的权值IDC_EDIT_13IDC_EDIT_14IDC_EDIT_15 IDC_EDIT_23IDC_EDIT_24 IDC_EDIT_25IDC_EDIT_34IDC_EDIT_35ID

18、C_EDIT_45IDC_EDIT_MATRIX显示邻接矩阵IDC_EDIT_COUT显示遍历结果5.2 程序代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为12个Edit Box控件建立Member Variables，按Ctrl+w键进入MFC ClassWizard界面，选择Member Variables选项卡，可显示成员变量设置界面，如图5所示。图5 成员变量设置界面下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。(1).将基于控制台应用程序的头文件Queue.h、Graph.h加入到MFC工程

19、的头文件中，同时将控制台应用程序的源文件main.cpp改名为premain.h加入到MFC的头文件中，同时需要修改部分：a.删除main.cpp(premain.h)的主函数int main()。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(&qu

20、ot;%d ",i+1);Dstr+=temp; 两条语句。(2).在对话框类的实现文件课程设计MFCDlg.cpp加入#include "premain.h"(在premain.h中已经包含了”Queue.h”、”Graph.h”)，以实现在该文件中可使用Graph类。(3). 在对话框类的实现文件课程设计MFCDlg.cpp中加入Graph g(5,6);,构造一个5顶点的无向图。(4).如图所示：示意图双击邻接矩阵按钮、广度优先搜索按钮、清空按钮，分别为其建立响应函数：邻接矩阵的响应函数OnButtonLj()；广度优先搜索的响应函数OnButtonBfs(

21、)；清空的响应函数OnButtonClean()(5). 邻接矩阵的响应函数代码（OnButtonLj()）：void CMFCDlg:OnButtonLj() CString str1010;UpdateData(TRUE); g.edge01=m_e12; g.edge10=m_e12; g.edge02=m_e13; g.edge20=m_e13; g.edge03=m_e14; g.edge30=m_e14; g.edge04=m_e15; g.edge40=m_e15; g.edge12=m_e23; g.edge21=m_e23; g.edge13=m_e24; g.edge31=

22、m_e24; g.edge14=m_e25; g.edge41=m_e25; g.edge23=m_e34; g.edge32=m_e34; g.edge24=m_e35; g.edge42=m_e35; g.edge34=m_e45; g.edge43=m_e45;m_str_matrix="" UpdateData(0); for(int i=0;i<5;i+) for(int j=0;j<5;j+) strij.Format("%i,",g.edgeij); m_str_matrix+=strij; m_str_matrix+=&quo

23、t;rn" UpdateData(FALSE); UpdateData(FALSE); (6). 广度优先搜索的响应函数代码（OnButtonBfs()）：void CMFCDlg:OnButtonBfs() / TODO: Add your control notification handler code hereint x;CString str1010;UpdateData(TRUE); g.edge01=m_e12; g.edge10=m_e12; g.edge02=m_e13; g.edge20=m_e13; g.edge03=m_e14; g.edge30=m_e14;

24、 g.edge04=m_e15; g.edge40=m_e15; g.edge12=m_e23; g.edge21=m_e23; g.edge13=m_e24; g.edge31=m_e24; g.edge14=m_e25; g.edge41=m_e25; g.edge23=m_e34; g.edge32=m_e34; g.edge24=m_e35; g.edge42=m_e35; g.edge34=m_e45; g.edge43=m_e45;g.Dstr=""g.BFS();m_str_cout=""UpdateData(FALSE);for(x=0;

25、x<5;x+)m_str_cout+=g.Dstr.GetAt(2*x)+'0'm_str_cout.MakeUpper();UpdateData(FALSE);(7). 清空的响应函数代码（OnButtonClean()）void CMFCDlg:OnButtonClean() / TODO: Add your control notification handler code hereUpdateData(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_e4

26、5=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

27、单击广度优先遍历按钮后的界面单击清空按钮后，对话框的编辑框内容全部置零，如图9所示。图8 单击清空按钮后的界面单击退出按钮后，程序能够正常实现退出。结 论本次课程设计作为编写Windows程序的初步尝试，能够实现程序的主要功能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标，本此编写的MFC程序虽然能实现所需功能，但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足，程序员可以此为例多加实践，达到能熟练掌握的效果。MFC为Windows应用程序开发者提供了一种快速开发的工具，尤其是MFC中提供的多种标准控件，使得开发者不再将过多的心思花在界面代码编写上，而将更多的精力投入到应用程序的