谁有好的DFS和BFS资料

想仔细学一下DFS和BFS，大家有好的资料推荐吗？视频或者blog?

利口那么多题目，做个几十道，想不会都难

非著名农民 发表于 2022-1-31 22:07
利口那么多题目，做个几十道，想不会都难

好吧，知道个大概的概念，想着大家有系统的资料

上学的时候的教材，Introduction to Algorithms, 3rd Edition (The MIT Press) https://www.amazon.com/dp/026203...JAABNTKEVWFG6VMTX6S

九z，古城都可以，大概知识点：

### BFS
1. 基础模板
2. 双端BFS。如果单边BFS时间复杂度为O(N), 双端为O(sqrt(N))
3. 不同模板易错点，比如 for (neighbor : curr.getNeighbors()) 是（1）遍历完neighbors后visit.add(curr)  还是（2）遍历一个neighbor后 visit.add(neighbor)

使用场景
1. 连通性：是否能到达或者走通
2. 最短路：BFS天然找到最短路
3. 拓扑排序：course schedule


### DFS
1. 基础模版
2. DFS 剪枝（如果没必要往下走了就return）

使用场景
1. 所有方案
2. 最短路（因为有1，所以能2）
3. 排列组合


另外，有一些题看上去不像是图数据结构那么明显，比如 类似华容道那个题， 3*3棋盘，现在是这个状态，求最少多少步到另一个状态。感觉需要抽象能力和经验累积