广度优先搜索算法（英语：Breadth-First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。 ## 实现方法 1. 首先将根节点放入队列中。 2. 从队列中取出第一个节点，并检验它是否为目标。 - 如果找到目标，则结束搜索并回传结果。 - 否则将它所有尚未检验过的直接子节点加入队列中。 3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。 4. 重复步骤2。 ## 伪代码 ```text BFS(root) Pre: root is the node of the BST Post: the nodes in the BST have been visited in breadth first order q ← queue while root = ø yield root.value if root.left = ø q.enqueue(root.left) end if if root.right = ø q.enqueue(root.right) end if if !q.isEmpty() root ← q.dequeue() else root ← ø end if end while end BFS ``` ## 参考 * [Wikipedia](https://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2) * [广度优先搜索](https://www.zhihu.com/topic/20336539/intro)