安可林文章网新闻资讯
广度优先算法(Breadth-First Search)，同广度优先搜索，又称作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索演算法。简单的说，BFS是从根节点开始，来自沿着树的宽度遍历树的节点，如果发现目标，则演算终止。广度优先搜索的实现一般采用open-closed表。
- 中文名称 广度优先算法
- 外文名称 Breadth-First Search
- 词性 名词
- 范畴 数学;计算机科学
思想
BFS是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。B来自FS并不使用经验法则算法。
从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的伫列中。一般的实作里，其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中(例如伫列或是链表)，而被检验财绝界文永简别推你过的节点则被放置在被称为cl360百科osed的容器中。(称open-closed表)
实现
所谓广度，就是友思由家一层一层的，向下遍历缺十良以月历留觉一，层层堵截，还是这幅图写步孩势月模占，我们如果要是广度优先遍历的话，我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。
1、访问顶点vi ;
2、访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ;
3、依次从这些邻接点(在步骤②中访问的顶点)出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问;
分来自析
空间复杂度
因为所有节点都必须被储存，因此BFS的空间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图360百科中边的数目。注:另一种说法称BFS的空间复杂度为O(B^M)，其中 B 是最大分支系数，而 M 是树的最长路径长度去未些改分门先苗。由于对空间的大量需求，因此B烈阿引压陈策病促序FS并不适合解非川其常大的问题。
时间复杂度
最差情形下，BFS必须寻找坏委席千甲裂社压婷那右所有到可能节点的所有路径，因此其时间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。
完全性
广度优有吸夜解置来门歌第安与先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则力论置笑有BFS将不收敛(不会结束)。
最佳解
若所有边的长度相等，广度优先搜索算法是最佳解--亦即它找到的第一个解，距离根节点的边数目一定最少;但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图(亦即各边长度不同)时，BFS仍然回传从根节点开始，经过边数目最少为击轮冷格的解;而这个解距离根节点的距离不一定最短。这个局章敌住止个问题可以使用考虑各边权值，BFS的改良算法成本一致搜寻法(en:uniform-cos谈误征航装八夫附黄t search)来解决。然而，若非加权图形，则奏决种争善方好所有边的长度相等，BFS就能找到最近的最佳解。
应用
广度优先搜索算法能用来解正论女头许可书决图论中的许多问题，例如:
寻找图中所有连接元件(Connected Component)。一个连接元件是图中的最大相连子图。寻找连接元件怎低中的所有节点。寻找非加该权图中任两点的最短路径。测试一图是否为二分图。(Reverse) Cuthill–McKee算法
寻找连接元件
由起点开始，执行广度优先搜索算法后所经过的所有节点，即为包所简跑系各刘病干含起点的一个连接元件。
测试是否二分图
BFS 可以用以测试二分图。从任一节点开始搜寻，并在搜寻过程中给节点不同的标签。例如，给开始点标签 0，开始点的所有邻居标签 1，开始点所有邻居的邻居标签0……以此类推。轴达角切例盐大证远若在搜寻过程中，任一节点有跟其相同标签的邻居，则此图就不是二分图。若搜寻结束时这种情形未发生，则此图为一二分图。
应用于电脑游戏中平面网格
BFS 立台外故防牛响阶测不保可用来解决电脑游戏(步士着设说类意和例如即时策略游戏)中找寻路径的问题。在这个应用中，使用平面网格来代替图形，而一个格子即是图中的一个节点。所有节点都与它的邻居(上、下、左、右、左上、右上、左下、右下)相接。
值得一提的是，当这样使用BFS算法时，首先要先检验上、下、左、右的邻居节点，再检验左上、右上、左下、右下的邻居节点。这是因为BFS趋向于先寻找斜向邻居节秋入室接重矛毛巴掉点点，而不是四方的邻居节点，因此找到的路径将不正确。BFS 应该先寻找四方邻居节点，接着才寻找斜向邻居节点1。