基于bfs算法的图的遍历设计与实现大学论文.doc

《基于bfs算法的图的遍历设计与实现大学论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、沈阳理工大学课程设计专用纸0摘要本文采用图的邻接矩阵实现了最短路径问题中图的存储；采用队列实现了图的广度优先搜索（BFS），用类的成员函数实现了其各个功能。本C++程序实现了图的最短路径存储及BFS遍历，采用Visual C++ 6.0的控制台工程和MFC工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的广度遍历程序，通过对两种程序的测试结果表明：基于BFS算法的图的遍历算法原理正确，两种程序均能正确求解给定的图的遍历问题。关键词:邻接矩阵；队列；广度优先搜索；控制台工程；MFC图形界面II沈阳理工大学课程设计专用纸目

2、录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参考文献23II沈阳理工大学课程设计专用纸1需求分析(1)图的应用和研究可追溯到18世纪。1736年，被称为图论之父的欧拉解决了哥尼斯堡（Konigsberg）问题，从而奠定了图论这门学科及其应用的基础。(2

3、)图作为一种非线性数据结构，被广泛应用与多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，在这些技术领域中把图结构作为解决的数学手段之一。(3)程序测试数据来自姜学军李筠主编的《数据结构（C语言描述）》中，所选的无向图是:13265748图122沈阳理工大学课程设计专用纸1算法基本原理2.1邻接矩阵邻接矩阵是表示节点之间的相邻接关系的矩阵。若G是有n个节点的图，则G的邻接矩阵是如下定义的nXn矩阵。如图所示图G的邻接矩阵如下：21011110101101101043图GG的邻接矩阵

4、22沈阳理工大学课程设计专用纸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出队，由于它们的邻接顶点都被访问过；此时队空，表示搜索已结束。22沈阳理工大学课程设

5、计专用纸1类设计3.1类的概述本题设计的关键是对图的广度优先搜索算法的设计，由于使用邻接矩阵来存储图，就要将广度优先搜索的算法扩展到矩阵中。首先应设计无向图类Graph然后设计成员变量，用二维数组edge来表示图边的权值，一维数组vertex来表示顶点信息，eNum来表示边的数量，vNum来表示顶点数量，以及在遍历中需要的访问标记数组visited。最后还要设计成员函数实现对邻接矩阵的输出print()，广度优先搜索函数BFS()。考虑到图的初始化比较复杂，需要Graph(inta,intb)输入各个顶点信息，intIn

6、itGraph()输入每条边的权值。由于调用BFS()需要用到队列，还需要设计结点类QueueNode和队列类LinkQueue；用data表示结点数据，*next表示结点指针域，使用构造函数QueueNode()对结点进行初始化;用*front和*rear表示队列的前驱和后继，使用voidInit_Queue()对队列进行初审，判断队列是否为空:voidInit_Queue(),入队类操作:intEn_Queue(DataTypee),出队列操作:voidDe_Queue(DataType&e)。由于程序比较复杂，Gr

7、aph类的接口实现放在Graph.h中,QueueNode类和LinkQueue类的接口放在Queue.h中，类的实现和主函数放在main.cpp中。3.2类的接口设计**************************************************************************************//Graph.hGraph类的接口设计usingnamespacestd;constintmaxnum=100;//设置邻接矩阵的最大阶数classGraph{private:char

8、vertex[maxnum];//图的顶点信息intedge[maxnum][maxnum];//图的边信息intvNum;//顶点个数inteNum;//边的个数boolvisited[maxnum];//标记这个顶点是否被访问过,0表示没有,1表示已经被访问过public:Graph(inta,intb);//构