广度优先搜索,即BFS(Breadth First Search),常常与深度优先搜索并列提及。这是一种相当常用的图算法,其特点是:每次搜索指定点,并将其所有未访问过的近邻加入搜索队列(而深度优先搜索则是栈),循环搜索过程直到队列为空。
仍以深度优先搜索中的图为例(但是希望各位不要产生深搜和广搜只能用于无向图的错觉):
B--E
/
A-C--F
>H
D--G
如上图(H是和F,G相连的,空格被吃掉),从A点发起一次广度优先搜索,则可以得到如下搜索结果:
当前点 搜索队列
A 初始队列为空,具体编码可以灵活掌握。
BCD
B CD
CDE
C DE
DEF
D EF
EFG
E FG
FG
F G
GH
G H
H
H 队列空。
应用:无权最短路。