深度优先搜索(Depth-First-Search,简称DFS)是一种用于遍历或搜索树或图的算法,其思想是从一个顶点 V0 开始,沿着一条路一直走到底,如果发现不能到达目标解,就退回到上一步的状态,转向另一条路径进行探索,直至找到目标解。
文章目录
- 深度优先搜索的过程
- DFS在LeetCode的应用
深度优先搜索的过程
深度优先搜索按照深度的方向进行搜索,先尽可能地沿着一条路走到底,走不通时再回溯到前一个节点,转向下一条路,继续探索,直到所有的节点都访问到,或者找到目标解。其搜索过程可以用一个堆栈来实现,通常用递归的方式来编写算法。
DFS在LeetCode的应用
让我们以LeetCode上的一个例题来展示深度优先搜索的应用:题目编号200,题目名称“岛屿数量”。
问题描述如下:
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。(岛屿指的是由水围绕的陆地。)
这是一个标准的深度优先搜索题目,解题的思路是我们可以将二维网格看成一个无向图,竖直或水平相邻的 1 之间有边相连。
对于每一个土地格子,我们通过DFS算法寻找每片“岛屿”并将其标记剔除,然后统计可以寻找到的岛屿数量。
下面是该问题的Python代码实现:
class Solution:def numIslands(self, grid: List[List[str]]) -> int:if not grid:return 0count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':self.dfs(grid, i, j)count += 1return countdef 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':returngrid[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’,则将其加入岛屿计数并将其淹没。接下来,我们通过深度优先搜索淹没与之相连的所有陆地,这样我们可以确保每个岛屿只被计数一次。