《基于BFS算法的图的遍历设计与实现(共24页)》由会员分享，可在线阅读，更多相关《基于BFS算法的图的遍历设计与实现(共24页)（25页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上0摘 要本文采用图的邻接矩阵实现了最短路径问题中图的存储；采用队列实现了图的广度优先搜索（BFS），用类的成员函数实现了其各个功能。本C+程序实现了图的最短路径存储及BFS遍历，采用VisualC+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 11 0 1 043 图G
3、 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表示结点指针域，使用构造函数Que
5、ueNode()对结点进行初始化;用*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 namespace std; c
6、onst 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;while(p)q=p;p=p-
8、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) /判断是否申请成功p-data=e;if(rear)rear-n
9、ext=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边数b的无向图endl; vNum=a; eNum=b; /为了防止原先存在e中的数据对今后的搜索造成影响,所以对其进行初始化 for(int i=0;i vNum;i+) f
10、or(int j=0;j vNum;j+) edgeij = 0; int Graph:InitGraph() int i,j,temp,flag=0; for (i=0;ivNum;i+) cout请输入第i+1vertexi; /输入各个边的具体情况 cout请输入各个边的权值endl; for (i=0;ivNum;i+) for(j=i+1;jvNum;j+) coutvertexivertexjtemp; edgeij=temp; edgeji=temp; if(temp)flag+; if(flag=eNum) cout初始化无向图邻接矩阵完毕endl; return 0; ret
11、urn 1; /输出邻接矩阵 void Graph:print() cout邻接矩阵为endl; int i,j; for (i=0;ivNum;i+) for (j=0;jvNum;j+) coutedgeij ; coutendl; void Graph:BFS()cout广度优先搜索（BFS）endl;int i,j;LinkQueue Q;/生成辅助队列对象Qfor(i=0;ivNum;+i)visitedi=false;/访问标志数组初始化Q.Init_Queue();/初始化队列Qfor(i=0;ivNum;+i)if(!visitedi)/对未访问的顶点进行收缩visitedi=true;coutvertexi ;Q.En_Queue(i);while(!Q.Empty_Queue()/队列非空
