[AIGC] 深度优先搜索（DFS）详解及其在LeetCode问题中的应用

深度优先搜索（Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法，其思想是从一个顶点 V0 开始，沿着一条路一直走到底，如果发现不能到达目标解，就退回到上一步的状态，转向另一条路径进行探索，直至找到目标解。

---

深度优先搜索的过程

深度优先搜索按照深度的方向进行搜索，先尽可能地沿着一条路走到底，走不通时再回溯到前一个节点，转向下一条路，继续探索，直到所有的节点都访问到，或者找到目标解。其搜索过程可以用一个堆栈来实现，通常用递归的方式来编写算法。

DFS在LeetCode的应用

让我们以LeetCode上的一个例题来展示深度优先搜索的应用：题目编号200，题目名称“岛屿数量”。

问题描述如下：
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。(岛屿指的是由水围绕的陆地。)

这是一个标准的深度优先搜索题目，解题的思路是我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。

对于每一个土地格子，我们通过DFS算法寻找每片“岛屿”并将其标记剔除，然后统计可以寻找到的岛屿数量。

下面是该问题的Python代码实现：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

在以上代码中，我们首先扫描整个二维网格。如果一个位置为 ‘1’，则将其加入岛屿计数并将其淹没。接下来，我们通过深度优先搜索淹没与之相连的所有陆地，这样我们可以确保每个岛屿只被计数一次。