DFS:
排列数字
n-皇后


  1. 深度优先搜索通常需要使用布尔值来记录某个元素是否被遍历过
  2. 深度优先搜索需要注意状态的回溯, 每当进入更深层的DFS时,需要在进入之前改变元素的遍历状态, 当从更深层DFS中弹出时, 需要将之前改变的元素状态复位;
  3. 对于n皇后之类的棋盘问题,可以考虑使用建立坐标系的方式构建直线来使用对角线、反对角线等辅助线来解题。

BFS:
走迷宫
八数码


  • 广度优先遍历的通用模板:
    1
    2
    3
    4
    5
    6
    7
    8
    while(队列不空)
    {
    auto t = 队头元素
    遍历队头元素所能到达的元素,并加入队列中
    并根据题目维护不同的额外信息
    }

    队列为空时,说明深度遍历已经结束
  • BFS中通常涉及到上下左右方向的枚举,可以直接使用两个数组dx dy来模拟

树和图的DFS:
数的重心

树和图的BFS:
图中点的层次


  1. 树和图的存储方式有邻接表和邻接矩阵两种,稀疏图可以使用邻接表,稠密图则需要使用邻接矩阵存储
  2. 邻接表模板:
    1
    2
    3
    4
    5
    6
    7
    8
    int 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 ++;
    }
  3. 遍历模板(DFS 与 BFS 类似):
    1
    2
    3
    4
    5
    for(int i = h[u]; i != -1; i = ne[i])
    {
    int j = e[i];
    // 根据DFS BFS的不同,使用不同的具体策略
    }

拓扑排序:
有向图的拓扑序列

  • 在拓扑排序中,需要借助出度、入度的概念维护相应的信息,并借此通过BFS解题。