算法之深度优先搜索（DFS）

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历节点，尽可能深地探索每个分支，直到达到叶子节点或无法继续深入为止，然后回溯，探索下一个分支。DFS 在解决诸如图的连通性、拓扑排序、回路检测等问题上展现出其独特优势。本文旨在深入探讨 DFS 的原理、实现、特性及实际应用案例，帮助读者全面掌握这一重要算法。

1. 原理与算法描述

1.1 基本概念

DFS 的核心思想在于“深入到底，再回头”。算法从起始顶点出发，访问一个顶点后，先探索与之相连且未被访问过的顶点，直到到达一个叶子节点或无法继续深入，然后回溯到上一个顶点，继续探索其他未访问的分支。DFS 可以用于解决路径查找、图的连通性、拓扑排序等问题。

1.2 实现方法

DFS 可以通过递归或迭代两种方式实现：

递归：自然适合 DFS 的递归结构，每进入一个新顶点，就调用自身处理该顶点的邻接点，直至到达叶子节点或遇到已访问过的顶点返回。
迭代：使用栈来模拟递归过程，维护一个待访问顶点的栈，每次从栈顶取出顶点访问，然后将未访问的邻接顶点压入栈。

1.3 时间与空间复杂度

DFS 的时间复杂度一般为 O(V+E)，其中 V 是顶点数，E 是边数。在最坏情况下，需要访问每个顶点和每条边。空间复杂度取决于递归深度或迭代过程中使用的栈空间，最坏情况下为 O(V)。

2. 特性与应用场景

2.1 特性

深度优先：优先探索一条路径的尽头。
回溯：当一条路径走不通时，回退到上一节点，尝试其他路径。
剪枝：在某些问题中，DFS 可以提前终止不必要的探索，提高效率。
拓扑排序：DFS 可用于有向无环图（DAG）的拓扑排序，确定任务的执行顺序。

2.2 应用场景

图的连通性：判断图是否连通，找到所有连通分量。
回路检测：DFS 可以用来检测图中是否存在环。
迷宫求解：通过标记已访问路径，DFS 能有效地求解迷宫问题。
树的遍历：DFS 是树遍历的基本方法之一，包括前序、中序和后序遍历。
顶点间的最短路径：在特定类型的图中，如无权图，DFS 可以找到两点之间的路径（但不是最短路径）。

3. 实战案例：岛屿数量（LeetCode 200）

问题描述

给定一个二维网格地图，由'1'（陆地）和'0'（水域）组成，计算岛屿的数量。岛屿由水平或垂直相邻的陆地组成。

// 示例1：
const grid1 = [
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "0", "0", "0"],
];
// 输出：1

// 示例2：
const grid2 = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"],
];
// 输出：3

解决方案

算法思路

采用 DFS 遍历每个'1'（陆地），一旦遇到就标记为已访问，并递归探索其所有相连的陆地，直到该岛屿的所有部分都被访问过。使用一个计数器记录岛屿数量。

代码实现

var numIslands = function (grid) {
  let islandCount = 0;
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) {
      if (grid[row][col] == 1) islandCount += 1;
      dfs(grid, row, col); //从当前陆地开始DFS
    }
  }
  return islandCount;
};

// 深度优先搜索DFS，深入探索一个区域，直到无法继续前进，然后回溯
function dfs(grid, row, col) {
  if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] != 1)
    return;
  grid[row][col] = "2"; // 标记为已访问
  dfs(grid, row - 1, col); //上
  dfs(grid, row + 1, col); //下
  dfs(grid, row, col - 1); //左
  dfs(grid, row, col + 1); //右
}

分析

时间复杂度：O(M*N)，M 为行数，N 为列数，每个单元格最多被访问一次。
空间复杂度：O(M*N)，在最坏情况下，DFS 的递归深度达到 MN，考虑递归栈的开销。

通过这个案例，我们可以看到 DFS 是如何有效地解决特定问题的，尤其是在探索和遍历具有递归结构的图或网格时表现出色。理解 DFS 的机制和应用，对于算法学习和解决实际问题至关重要。