20211106刷题记录
- 深度优先搜索通常需要使用布尔值来记录某个元素是否被遍历过
- 深度优先搜索需要注意状态的回溯, 每当进入更深层的DFS时,需要在进入之前改变元素的遍历状态, 当从更深层DFS中弹出时, 需要将之前改变的元素状态复位;
- 对于n皇后之类的棋盘问题,可以考虑使用建立坐标系的方式构建直线来使用对角线、反对角线等辅助线来解题。
- 广度优先遍历的通用模板:
1
2
3
4
5
6
7
8while(队列不空)
{
auto t = 队头元素
遍历队头元素所能到达的元素,并加入队列中
并根据题目维护不同的额外信息
}
队列为空时,说明深度遍历已经结束 - BFS中通常涉及到上下左右方向的枚举,可以直接使用两个数组dx dy来模拟
树和图的DFS:
数的重心树和图的BFS:
图中点的层次
- 树和图的存储方式有邻接表和邻接矩阵两种,稀疏图可以使用邻接表,稠密图则需要使用邻接矩阵存储
- 邻接表模板:
1
2
3
4
5
6
7
8int h[N], e[N], ne[N], idx;
memset(h, -1, sizeof h);
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
} - 遍历模板(DFS 与 BFS 类似):
1
2
3
4
5for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
// 根据DFS BFS的不同,使用不同的具体策略
}
拓扑排序:
有向图的拓扑序列
- 在拓扑排序中,需要借助出度、入度的概念维护相应的信息,并借此通过BFS解题。
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.