基于队列广度优先遍历算法设计和实现

《基于队列广度优先遍历算法设计和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于队列广度优先遍历算法设计和实现摘要：本文主要介绍在二维数组邻接矩阵存储结构下下利用队列对无向连通稠密图进行广度优先遍历的算法设计及实现过程，文中给出了算法思想,［法设计思路及具体实现代码。关键词：广度优先；队列；遍历；邻接矩阵中图分类号：TP311.12图是一种重要的非线性数据结构,在计算机中的物理存储方式主要有邻接矩阵和邻接表两种,其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。对图进行遍历是依次访问图中所有顶点和边的一种系统方法，即对非线性结构进行线性化的过程，图的遍历算法主要有广度优先、广度优先和最佳优先3种，本文仅以图1所示的无向连通稠密图为例，采用图2所示的二

2、维数组邻接矩阵作为存储结构，介绍广度优先遍历算法的设计和实现方法。图1无向联通图图2图的邻接矩阵存储示意图1广度优先遍历思想广度优先遍历将图中顶点分成若干层次，以行分层访问。遍历过程为:（1）从图中任一顶点v开始，当顶点v未被访问过时,作访问标记；（2）遍历v所有未被访问的邻接点vl,v2,vk,作访问标记；（3）依次访问vl,v2,vk未被访问的邻接点，作访问标记；继续依次访问各邻接点未被访问的邻接点，直到没有未被访问的邻接点为止。2广度优先的遍历算法本文的广度优先遍历算法借助队列实现，算法设计基本思路如下：（1）初始化队列；（2）对所有节点作未访问标记；（3）起始节点

3、入队列；（4）当队列不为空时：1）队首顶点v出队；2）如果顶点v未标记为已访问，贝＞］：①打印v；②标记v为已访问；③遍历顶点V的邻接点，如果邻接点U未被标记为已访问，则u入队列。对于一个含有V个顶点的无向连通图，广度优先遍历的非递归算法在最好的情况下（每个顶点仅有两条边相连）每个顶点仅被访问一次，时间复杂度为0（n）；而在最坏的情况下(图为完全图时)，搜索第i层结点时将会有n-i个结点入队列，最多在队列中存储(n-2)*(n-l)/2个结点，此时的时间复杂度与递归算法类似，为0(n2)。基于队列的广度优先遍历算法具体程序代码如下：privatevoidBFVisit(i

4、ntprev,intv){Queueq=newQueue()；//建立存储队列id二0；for(inti=l；i<=V；i++)visitedCi]=0；//对所有顶点作未访问标记q.enqueue(v)；//顶点v入队Console.WriteLine(”BFsearchbyqueue：”)；wh订e(!q.isEmpty()){//设置循环结束条件为队列空v二q.deQueue()；//队首元素v出队Console.WriteLine(”{0}-”，v)；if(!visited[v]){//如果顶点v未被访问过visited[v]=++id；//设置顶点v的访问标记f

5、or(intu=l；u<=V；u++){//对顶点v所有未被访问的邻接点执行入队操作if(visited[u]==0&&adj[v,u]!=0)q.enQueue(u)；利用广度优先遍历的非递归算法BFVisit()对图1进行遍历时，顶点的遍历过程及相应队列状态如图3所示。图3中，新入队的邻接点用深色背景表示，如当遍历顶点A的邻接点时，B.C、D、G顶点先后入队。图3遍历过程及队列状态3结束语我们可以以任意顺序访问当前顶点的邻接点，因此图的广度优先遍历结果不唯一。但在具体的算法设计和实现过程中，我们需要应用某种具体存储结构来存储和表示图，进而设定特定的访问规则进行遍历，从

6、而得到唯一的遍历结果，如本文我们利用DFVisit()算法对图1进行广度优先遍历时，遍历的结果始终是A-B~C_D~G_E_H-F。参考文献：[1]胡佳，赵福生•广度优先搜索在迷宫问题中的应用[J].江西教育学院学报，2013(02).[2]杜恒.图的广度优先遍历的算法实现[J].南阳师范学院学报，2012(12).[3]欧阳圣，胡望宇.几种经典搜索算法研究与应用[J].计算机系统应用，2011(05).[4]严蔚敏•数据结构[M]・北京：清华大学出版社，1997.[5]MichaelTGoodRich,Data,Structures&AlgorithmsinC++,Jo

7、hnWiley&Sons,Inc.作者简介：王鹏程（1992.05-）,男，北京人，计算机专业，本科；李光杰（1980.09-）,女，辽宁朝阳人，副教授，硕士，研究方向：软件工程。作者单位：北京工业大学耿丹学院信息工程系，北京101301