图搜索算法:广度优先查找 gaunthan Posted on Feb 17 2017 ? Searching ? ? Algorithm ? > **广度优先查找**(Breadth First Search, BFS)与[深度优先查找](http://leanote.com/blog/post/58a65061ab64414b060026d9)一样,是穷举查找、无信息图查找算法的一种,用来系统地遍历图中的所有顶点和边。 ## 思想 如果说深度优先查找遍历表现出来的是一种勇气(该算法尽可能地离“家”远些),那么广度优先查找遍历表现出来的则是一种谨慎。它按照一种同心圆的方式,首先访问所有和初始顶点邻接的顶点,然后是离它再远一步的所有未访问顶点,以此类推,直到所有与初始顶点在同一个连通分量中的顶点都访问过了为止。如果仍然存在未被访问的顶点,该算法必须从图的其他连通分量中的任意顶点重新开始。 广度优先查找需要借用到队列来实现。该队列先从遍历的初始顶点开始,将该顶点标记为已访问。在每次迭代的时候,该算法找到所有和队头顶点邻接的未访问顶点,把它们标记为已访问,再把它们入队。然后,将队头顶点从队列中除去。 ## 示例 示例如下: [^BFS Sample] [^BFS Sample]:[C++ :: Breadth-first search algorithm (BFS)](http://nbangla.blogspot.com/2012/12/c-breadth-first-algorithm-bfs.html). ## 伪代码 以下是深度优先查找遍历的伪代码,它能够输出每个顶点第一次被遍历的顺序: ```cpp // 实现给定图的广度优先查找遍历 // @input 图G = <V, E> // @output 图G的顶点,按照被访问到的先后次序用整数标记 BFS(G) 将V中的每个顶点标记为0,表示还未被访问 count = 0 for each v vertex in V do if v is marked with 0 bfs(v) // 访问所有和v相邻接的未访问顶点,然后按照count的值给它们标序 bfs(v) ++count; mark v with count initialize a queue with v while the queue is not empty do for each vertex w in V adjacant to the front vertex do if w if marked with 0 ++count; mark w with count add w to the queue remove the front vertex from the queue ``` ## 效率分析 广度优先查找和深度优先查找的效率是相同的: - 对于邻接矩阵表示法,它属于$\theta(|V|^2)$; - 而对于邻接链表表示法,它属于$\theta(|V|+|E|)$。 和深度优先查找不同的是,广度优先查找只产生顶点的一种排序。因为队列是一种FIFO结构,所以顶点入队的次序和它们出队的次序是相同的。 ## 应用 ### 二叉树的层次遍历 二叉树有三种遍历方式:先序遍历、中序遍历以及后序遍历。实际上,我们还可以实现一种结构化的遍历方式:层次遍历。层次遍历在实现二叉树的可视化时非常有帮助。树的层次遍历算法实际上就是广度优先查找遍历。 ### 检查图的连通性和无环性 BFS也可以检查图的连通性和无环性,做法在本质上和DFS是一样的。 ### 求两个给定顶点的最少边路径 从两个给定顶点中的一个开始BFS遍历,一旦访问到了另一个顶点就结束。这时候我们的遍历顺序将生成一棵树,该树的根结点是起始顶点。树根到另一个给定顶点的路径,就是所求的、边数量最少的路径。 ## See Also - [图搜索算法:深度优先查找](http://leanote.com/blog/post/58a65061ab64414b060026d9) ## References - 莱维汀, A.). 算法设计与分析基础(第3版)[M]. 清华大学出版社, 2015. 赏 Wechat Pay Alipay 选择排序(Selection sort) 图搜索算法:深度优先查找