广度优先搜索(Breadth-First-Search)
在树(图/状态集)中寻找特定节点
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807431751-1024x461.png)
How the BFS would work
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807444621.png)
BFS 模板代码:倾向于队列
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807451830.png)
需要注意的地方:对于树可以省略 visited ,如果是图的话不能省略。原因:树不会重复,图是会重复的。
深度优先搜索(Depth-First-Search)
How a DFS Would Traverse This Tree
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807510784-1024x585.png)
图的遍历:
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807550511.png)
DFS代码 – 递归写法模板 :
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807522149-1024x583.png)
DFS代码 – ⾮递归写法模板:倾向于栈
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807541494.png)
两者对比:
![](https://i.lckiss.com/wp-content/uploads/2020/08/2020081807520218-1024x419.png)
相关题目:
内容来自极客时间《算法面试通关40讲》
本站由以下主机服务商提供服务支持:
0条评论