简介
广度优先搜索算法(英语: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)
一起来交流一下吧~
评论加载中...
Copyright © 2022-2023 1024Code 粤ICP备19030132号-9