【学习笔记】DFS与BFS

这是OI竞赛中两个基础算法，在此做一个简略的总结

DFS

全名深度优先搜索，顾名思义，是深度优先，一条路走到黑的做法
树、图论相关的问题中常用到$DFS$遍历处理信息
算法用处：

• 暴力，一般题目总会在最低档的部分分设置用最无脑的dfs解决
• 遍历，用处比较大

BFS

全名宽度优先搜索
一般的套路是设置状态，既然是宽度优先，那么同一个状态越早到达越优
所以时空复杂度都是状态总数，常数不论
算法用处：

• 低级题目
• 一些题目的暴力会设置这个部分分

另外好像还有个叫做bfs树的东西，不是很熟悉
接下来纯属口胡

A

DFS与BFS结合的算法名为A算法
全名迭代加深搜索，先给定深度上界，在深度优先搜索
非常像DFS和BFS套起来
跟BFS相比较的话用时间换了空间

A*

A可能会出错，所以再来个估价函数，就变成A*啦

出现一大堆错误的口胡真快乐