是从根节点开始,沿着树的宽度遍历树的节点,如果发现目标,则算法中止。广度优先搜索的实现一般采用open-closed表。
BFS是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。
从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的伫列中。一般的实作里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如伫列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)
以德国城市为范例的地图。城市间有数条道路相连接。
从法兰克福开始执行广度优先搜索算法,所产生的广度优先搜索算法树。
广度优先搜索算法的动画范例 实作方法
while
从Q中选一点
/* 选最先插入进Q的点,则为广度遍历,可以说先进先出。*/
/* 选最后插入进Q的点,则为深度遍历,可以说后进先出。 */
if then /* N(v):v的邻接点 */
else
return H=(R,T)
广度优先搜索算法:
v QMPTYQ w visited /*頂點w對應的訪問標記置為1*/
}
W = NEXTADJ(G,v); /*求v的下一個鄰接點。若無鄰接點則返回-1*/
}
}
}
对图G=(V,E)进行广度优先搜索的主算法如下。
visitedni i i visited
}
定义一个结构体来表达一个节点的结构:
node
那么,我们在搜索一个树的时候,从一个节点开始,能首先获取的是它的两个子节点。例如:
AB C
A是第一个访问的,然后顺序是B和C;然后再是B的子节点,C的子节点。那么我们怎么来保证这个顺序呢?
这里就应该用queue数据结构,因为queue采用先进先出( first-in-first-out )的顺序。
使用C++的STL函式库,下面的程序能帮助理解:
stdnode
nodenodes
unvisited.
left
unvisited.left
right
unvisited.rightcurrentcurrent
}
因为所有节点都必须被储存,因此BFS的空间复杂度为 O(|V| + |E|),其中 |V| 是节点的数目,而 |E| 是图中边的数目。注:另一种说法称BFS的空间复杂度为 O(BM),其中 B 是最大分支系数,而 M 是树的最长路径长度。由于对空间的大量需求,因此BFS并不适合解非常大的问题。
时间复杂度最差情形下,BFS必须寻找所有到可能节点的所有路径,因此其时间复杂度为 O(|V| + |E|),其中 |V| 是节点的数目,而 |E| 是图中边的数目。
完全性广度优先搜索算法具有完全性。这意指无论图形的种类如何,只要目标存在,则BFS一定会找到。然而,若目标不存在,且图为无限大,则BFS将不收敛(不会结束)。
最佳解若所有边的长度相等,广度优先搜索算法是最佳解——亦即它找到的第一个解,距离根节点的边数目一定最少;但对一般的图来说,BFS并不一定回传最佳 解。这是因为当图形为加权图(亦即各边长度不同)时,BFS仍然回传从根节点开始,经过边数目最少的解;而这个解距离根节点的距离不一定最短。这个问题可 以使用考虑各边权值,BFS的改良算法成本一致搜寻法(en:uniform-cost search)来解决。然而,若非加权图形,则所有边的长度相等,BFS就能找到最近的最佳解。
广度优先搜索算法的应用广度优先搜索算法能用来解决图论中的许多问题,例如:
寻找连接元件由起点开始,执行广度优先搜索算法后所经过的所有节点,即为包含起点的一个连接元件。
测试是否二分图BFS 可以用以测试二分图。从任一节点开始搜寻,并在搜寻过程中给节点不同的标签。例如,给开始点标签 0,开始点的所有邻居标签 1,开始点所有邻居的邻居标签二……以此类推。若在搜寻过程中,任一节点有跟其相同标签的邻居,则此图就不是二分图。若搜寻结束时这种情形未发生,则此图 为一二分图。
应用于电脑游戏中平面网格BFS 可用来解决电脑游戏(例如即时策略游戏)中找寻路径的问题。在这个应用中,使用平面网格来代替图形,而一个格子即是图中的一个节点。所有节点都与它的邻居(上、下、左、右、左上、右上、左下、右下)相接。
值得一提的是,当这样使用BFS算法时,首先要先检验上、下、左、右的邻居节点,再检验左上、右上、左下、右下的邻居节点。这是因为BFS趋向于先 寻找斜向邻居节点,而不是四方的邻居节点,因此找到的路径将不正确。BFS 应该先寻找四方邻居节点,接着才寻找斜向邻居节点。