深度优先搜索

定义

深度优先搜索, Deep First Search, 简称 dfs , 因其「一条路走到黑」的特性, 得此名字;
实际上 dfs 类似 暴力枚举, 列出所有可能路径, 尝试所有的路, 直到找出答案;
常用实现手段为 递归调用, 也有非递归方法, 但是递归更加方便
实现

模板

和递归函数一样, 需要有递归结束的边界条件, 以及不满足条件时需要执行的操作
需要有访问标志, 一般来说是用一个bool 数组

应用

探索连通路径

举例: 走迷宫可行解与最优解 ``` / 可行解版本 / char map[10][10]; bool vis[10][10]; //dfs 必备访问标志数组 bool dfs(int x, int y) { //首先写边界条件 if (map[x][y] == 终点) {
```
  return true;
```
} //否则执行暴力搜索操作并再次调用 vis[x][y] = true; //更新访问 int tx = x + 新操作; int ty = y + 新操作; //判断条件比如是否在地图内是否走过这一步是否能走这里 if (in(tx, ty) && map[tx][ty] != 墙壁 && !vis[tx][ty] ) {
```
  if (dfs(tx, ty)) {
      return true;
  }
```
} return false; }

```
/* 最优解版本 引入走了多少步这个参数 */
char map[10][10];
bool vis[10][10]; //dfs 必备访问标志数组
bool dfs(int x, int y,  int step) {
    //首先写边界条件
    if (map[x][y] == 终点) {
        return true;
    }
    //否则执行暴力搜索操作 并再次调用
    vis[x][y] = true; //更新访问
    int tx = x + 新操作;
    int ty = y + 新操作;
    //判断条件 比如 是否在地图内 是否走过这一步 是否能走这里
    if (in(tx, ty) && map[tx][ty] != 墙壁 && !vis[tx][ty] ) {
    //如果能走 则步数加1
        if (dfs(tx, ty, step + 1)) {
            return true;
        }
    }
    //值得注意的一个操作 是否要取消访问标志
    //取决于 求可行解 还是 最优解
    //最优解需要这一步
    //因为虽然走不通这个点 但这个点也有可能时最优解的一部分
    vis[x][y] = false;
    return false;
}

求连通分量个数

性质: 一个图如果完全连通, 则只需要一次 dfs 就能遍历所有点, 即有一个连通分量, 否则连通分量的个数为 dfs 的调用个数
举例: 踏青求草丛个数 “#”为草丛 ``` //输出 5 6 .#…. ..#… ..#..# …##. .#….

//输出 5

include

using namespace std; char map[105][105]; bool v[105][105]; int d[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; int ans = 0; int n, m; bool in(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; } void dfs(int x, int y) { int tx, ty; v[x][y] = 1; for (int i = 0; i < 4; i++) { tx = x + d[i][0]; ty = y + d[i][1]; if (in(tx, ty) && map[tx][ty] == ‘#’ && !v[tx][ty]) { dfs(tx, ty); //满足条件则再次调用继续搜索 } } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { scanf(“%s”, map[i]); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { //如果是连通图的话调用一次 dfs 所有点都被访问过 if (map[i][j] == ‘#’ && !v[i][j]) { dfs(i, j); ans++; //每调用一次记录一次 } } } cout << ans << endl;
return 0; }

```

深度优先搜索

深度优先搜索

深度优先搜索

定义

实现

应用

探索连通路径

求连通分量个数

include