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

沈阳巩俐大学课程设计专题论文0摘要本文利用图邻接矩阵来存储最短路径问题中的图。图的广度优先搜索(BFS)由队列实现，其功能由类的成员函数实现。该C程序实现了图的最短路径存储和BFS遍历。VisualC 6.0的控制台项目和MFC项目分别用于在桌面上显示邻接矩阵和实现图形的宽度遍历。两个程序的测试结果表明，基于BFS算法的图遍历算法在原理上是正确的，两个程序都能正确解决给定图的遍历问题。关键词：邻接矩阵；排队。广度优先搜索；控制台工程；MFC图形界面目录1需求分析12算法1的基本原理2.1邻接矩阵12.2图的遍历广度优先搜索(BFS)23级设计3类别3.1概述33.2类接口设计4实施3.3类54基于控制台的应用程序94.1主要功能设计94.2运行结果和分析105基于MFC的应用程序125.1图形界面设计125.2程序代码设计145.3运行结果和分析20结论22参考文献23二1需求分析(1)地图的应用和研究可以追溯到18世纪。1736年，被称为图论之父的欧拉解决了柯尼斯堡问题，从而为图论及其应用奠定了基础。(2)图形作为一种非线性数据结构，被广泛应用于许多技术领域，如系统工程、化学分析、统计力学、遗传学、控制论、人工智能、编译系统等领域，其中图形结构被作为解决问题的数学手段之一。(3)程序测试数据来自蒋学军、李俊编辑的数据结构（C语言描述），选择的无向图为：13265748图12算法的基本原理2.1邻接矩阵邻接矩阵是表示节点间邻接关系的矩阵。如果g是一个有n个节点的图，g的邻接矩阵是一个如下定义的nn矩阵。如图所示，图g的邻接矩阵如下：210 1 1 11 0 1 01 1 0 11 0 1 043图的邻接矩阵2.2图的遍历广度优先搜索(BFS)例如，有以下无向图：13265748操作步骤如下：(1)先输出1(1为起点)，1进入团队；(2) 1退出团队，因为1的相邻顶点2和3没有被访问过，输出2和3并把2和3放入团队；(3) 2个出队，2个相邻顶点1个；(4) 3退出团队，因为3的相邻顶点1已经被访问过，但是相邻顶点6和7还没有被访问过，输出6和7并把6和7放入团队；(5) 4个出队，因为4个相邻顶点中的2个已经被访问过但相邻顶点8没有被访问过，输出8并把8个入队；最后5、6、7、8个团队不在团队中，因为它们的相邻顶点已经被访问过。此时，团队是空的，表明搜索已经结束。3级设计类别3.1概述本课题设计的关键是图的广度优先搜索算法的设计。由于邻接矩阵用于存储图，因此广度优先搜索算法必须扩展到该矩阵。首先设计无向图类图，然后设计成员变量。二维数组边用于表示图边的权重，一维数组顶点用于表示顶点信息，eNum用于表示边的数量，vNum用于表示顶点的数量，遍历时需要访问标签数组。最后，设计了成员函数来实现输出print()到邻接矩阵，以及广度优先搜索函数BFS()。考虑到图初始化的复杂性，图(int a，int b)需要输入每个顶点的信息，int InitGraph()需要输入每个边的权重。因为调用BFS()需要队列、节点类队列节点和队列类链接队列；也需要设计。数据用于表示节点数据，*next用于表示节点指针字段，构造函数QueueNode()用于初始化节点。队列的前部和后部由*前部和*后部表示，首先使用void _ queue()检查队列，以确定队列是否为空： void _ queue()，队列进入操作： int En_Queue(数据类型e)，队列退出操作： void De _ Queue(数据类型e)。由于程序的复杂性，图形类接口的实现放在图形中，队列节点类和链接队列类的接口放在队列中，类和主函数的实现放在main.cpp中3.2级接口设计* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */图h图形类的界面设计使用命名空间标准；常量int maxnum=100/设置邻接矩阵的最大顺序类图private:char顶点maxnum；/图的顶点信息马克斯姆马克斯姆；/图的边信息int vNum/顶点数int eNum。/边数布尔拜访了马克斯纳姆；/标记该顶点是否被访问过，0表示没有，1表示被访问过public:图形(整数a，整数b)；/构造函数int InitGraph()；/图形类的初始化函数无效打印()；/输出邻接矩阵void BFS()；/广度优先遍历邻接矩阵；* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */队列. h队列节点类和链接队列类的接口设计：typedef int DataType。类排队节点public:数据类型数据。队列节点*下一个；排队节点()next=空；类链接队列public:队列节点*前端；队列节点*后部；LinkQueue() ；/构造函数空隙队列()/初始化前端=空；后部=空；LinkQueue()/析构函数QueueNode *p，*q。p=前部；而(p)q=p；p=p-下一个；删除q；前端=空；后部=空；int空队列()；/判断队列是否为空整型队列(数据类型e)；/队列操作无效队列(数据类型e)；/队列外操作；3.3级的实施/main.cppint linkqueue : empty _ Queue()返回(前=空后=空)；int链接队列：En_Queue(数据类型e)队列节点* p=新队列节点；如果(p) /判断应用程序是否成功p-数据=e；如果(后部)后部-下一个=p；否则前=后=p；返回1；其他返回0；void linkqueue : de _ Queue(数据类型e)queue node * p；如果(！空队列()p=前部；e=p-数据；front=front-next；如果(！前)后=空；删除p；图形：图形(int a，int b)“Cout”创建的顶点数是“