Toki
Why so serious?
图 搜索、存储
DFS
- 常使用递归+标记数组，在一个图上遍历
洛谷 P1706 全排列问题
- 深搜第k个输出位置
力扣200 网格搜索-岛屿数量
- 深搜陆地位置，可以填陆造海替代标记数组
BFS
- 常用队列，不要递归。只要递归就多少带点深搜的性质
- 基本上是从一个原点开始向周围扩散
洛谷P1443 马跑棋盘
- 这题居然卡常，无聊死了
- BFS的状态不一定要全局维护，也可以从上一个状态获取
洛谷P8693 大胖子走迷宫
- 忒难了
DFS&BFS优化：剪枝
- 减少对不合法、重复答案的枚举
- 常见的剪枝方法有：
减小状态空间、记忆化搜索
P1025 数的划分
- 剪除非法状态
P1464 Function
- 记忆化搜索，需要记忆先前状态
图存储
二维数组模拟邻接表
对于无权图，可直接将结点一维数组转换为二维数组：
vector 套 vector，省空间还有邻接表的优点
链式前向星
有权图无法用二维数组表示，可以使用边集数组+邻接表的逻辑：
这即是所谓的链式前向星
next 为 -1 表示没有元素