​​点击阅读更多查看文章内容

算法笔记——深度/广度优先搜索

深度优先搜索和广度优先搜索主要是用在图的遍历中，模板性很强，我个人认为是比较简单的算法，下面主要写一下深搜和广搜的模板，照着模板多做题基本就能掌握了

深度优先搜索

过程：

1. 访问指定的起始顶点
2. 若当前访问的顶点的邻接顶点有未被访问的,则选择其中一个顶点访问，然后回到第一步
3. 若当前的顶点的邻接顶点都已经访问，则返回当前顶点的上一个顶点

如下图，其实就是先沿一条边访问到底，然后再返回访问另一条边

模板

DFS一般通过递归来实现

 void dfs(int x){
    if (满足退出条件){ 
        退出处理
        return; 
    }
    for (;;){//枚举当前顶点的下一个邻接顶点
        if (顶点满足条件) {
            处理顶点
            dfs(顶点);//向下深入遍历
            }
    }
    return ;//退出 
}

这里在枚举下一个邻接顶点的时候，如果是在图中，我习惯先定义一个方向向量，然后以此来枚举下一个顶点
以上下左右四个方向为例：
首先定义：

int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

枚举：

for (int i = 0; i < 4; i++)
{
   dfs(x + fx[i][0], y + fx[i][1], board);
}

广度优先搜索

过程：

1. 访问指定的起始顶点
2. 将顶点的所有邻接顶点加入队列
3. 返回第一步访问队列的队首元素，队首元素弹出

如下图，先将当前顶点的邻接顶点都加入队列，然后再访问下一层的邻接顶点

模板

BFS一般通过队列来实现

queue<int> qu;//定义队列
      qu.push(起始顶点);
      while (!qu.empty())
      {
          auto front = qu.front();
          qu.pop();
          //获得首部顶点并将首部弹出

          for (;;)//遍历当前顶点的所有邻接顶点并加入队列
          {
              if (邻接顶点符合题目要求)
              {
                  qu.push(邻接顶点);
              }
          }
      }

以上模板仅仅是最基础的样例，不同的题目肯定还会有所不同，大家还要在模板的基础上结合题意进行进一步的修改

例题

1091. 二进制矩阵中的最短路径
130. 被围绕的区域