DFS, BFS
没有经典模板,重要的是顺序
搜索形式: 树 (不需要存储树,回溯隐藏在递归过程中)
应用: 对空间要求高的用DFS;求最短,最小的用BFS;思路奇怪的用DFS
DFS:
回溯:走到叶节点后回头;回溯时要恢复现场 (eg: 全排列)
剪枝:暴搜时跳过永远不可能为答案的情况 (eg: n-皇后)
BFS:
**!!!没懂为什么要用队列捏**
DP问题是一种特殊的最短路问题(没有环的最短路)
只有当所有边权都一样时,才可以用BFS求最短路
最短路有专门算法
基本形态:
树和图的遍历
树是一种特殊的图(树是无环连通图)
图
有向图
有方向 a -> b
存储:
邻接矩阵(开个二维数组)(用的较少,浪费空间 - n^2)
g[a, b]存储a -> b这条边信息,有权重值为权重值,无权重就是有无(bool), 无法存储重复边
作用:适合存储稠密图,稀疏图不好存
邻接表
应用最广
n个单链表,类似拉链法哈希法
每个点都有个单链表,单链表存这个点能走到的所有点(内部次序无所谓)
无向图(一种特殊的有向图)
无方向 a - b( a->b, b -> a)
既能从a到b也能从b到a,做的时候建两条
存储
遍历
拓扑排序
概念理解: 一路从小指向大,没有相反(成环)的有向图
做法:将所有入度为0的点入队,并利用bfs维护此队列,维护过程相当于每次把入度为0的点和边删掉