【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集：括号生成、岛屿问题、扫雷游戏

 《博主简介》

小伙伴们好，我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
✌更多学习资源，可关注公-仲-hao:【阿旭算法与机器学习】，共同学习交流~
👍感谢小伙伴们点赞、关注！

《------往期经典推荐------》

一、AI应用软件开发实战专栏【链接】
二、机器学习实战专栏【链接】，已更新31期，欢迎关注，持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】

DFS

括号生成

DFS class Solution:     def generateParenthesis(self, n: int) -> List[str]:         def DFS(left, right, s):             if left == n and right == n:                 res.append(s)                 return             if left < n:                 DFS(left+1,right,s+'(')             if right < left:                 DFS(left,right + 1,s+')')         res = []         DFS(0,0,'')         return res BFS class Node:     def __init__(self, left, right, s):         self.left = left         self.right = right         self.s = s class Solution:     def generateParenthesis(self, n: int) -> List[str]:         # BFS写法         res = []         if n == 0:             return res         queue = [Node(n,n,'')]         while queue:             node = queue.pop(0)             if node.left == 0 and node.right == 0:                 res.append(node.s)             if node.left > 0:                 queue.append(Node(node.left-1, node.right, node.s+'('))             if node.right > 0 and node.right > node.left:                 queue.append(Node(node.left, node.right-1, node.s+')'))         return res # 写法2： class Solution:     def generateParenthesis(self, n: int) -> List[str]:         # BFS写法         res = []         if n == 0:             return res         queue = [(n,n,'')]         while queue:             node = queue.pop(0)             if node[0] == 0 and node[1] == 0:                 res.append(node[2])             if node[0] > 0:                 queue.append((node[0]-1, node[1], node[2]+'('))             if node[1] > 0 and node[1] > node[0]:                 queue.append((node[0], node[1]-1, node[2]+')'))         return res

通常搜索几乎都是用深度优先遍历（回溯算法）。

广度优先遍历，得自己编写结点类，显示使用队列这个数据结构。深度优先遍历的时候，就可以直接使用系统栈，在递归方法执行完成的时候，系统栈顶就把我们所需要的状态信息直接弹出，而无须编写结点类和显示使用栈。

将BFS写法中的pop(0)改为pop()即为深度优先的迭代形式。

对比迭代的BFS写法与递归的DFS写法，可以看到，BFS其实是将DFS的参数当做队列中的一个元素来进行处理罢了，其他的与DFS没有什么区别。

并查集

岛屿问题

class Solution:     def numIslands(self, grid: List[List[str]]) -> int:         self.m = len(grid)         self.n = len(grid[0])         res = 0         for i in range(self.m):             for j in range(self.n):                 if grid[i][j] == '1':                     self.sink(i,j,grid)                     res += 1         return res          def sink(self, i, j, grid):         grid[i][j] = '0'         for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:             if 0<=ni<self.m and 0<=nj<self.n and grid[ni][nj] == '1':                 self.sink(ni,nj,grid)

扫雷游戏

# DFS class Solution:     def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:         # DFS         i, j = click         row, col = len(board), len(board[0])         if board[i][j] == "M":             board[i][j] = "X"             return board         # 计算空白快周围的雷数量         def cal(i, j):             res = 0             for x in [1, -1, 0]:                 for y in [1, -1, 0]:                     if x == 0 and y == 0: continue                     if 0 <= i + x < row and 0 <= j + y < col and board[i + x][j + y] == "M": res += 1             return res         def dfs(i, j):             num = cal(i, j)             if num > 0:                 board[i][j] = str(num)                 return             board[i][j] = "B"             for x in [1, -1, 0]:                 for y in [1, -1, 0]:                     if x == 0 and y == 0: continue                     nxt_i, nxt_j = i + x, j + y                     if 0 <= nxt_i < row and 0 <= nxt_j < col and board[nxt_i][nxt_j] == "E": dfs(nxt_i, nxt_j)         dfs(i, j)         return board # BFS class Solution:     def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:         i, j = click         row, col = len(board), len(board[0])         if board[i][j] == "M":             board[i][j] = "X"             return board         # 计算空白块周围的雷数目         def cal(i, j):             res = 0             for x in [1, -1, 0]:                 for y in [1, -1, 0]:                     if x == 0 and y == 0: continue                     if 0 <= i + x < row and 0 <= j + y < col and board[i + x][j + y] == "M": res += 1             return res         def bfs(i, j):             queue = [(i,j)]             while queue:                 i, j = queue.pop(0)                 num = cal(i, j)                 if num > 0:                     board[i][j] = str(num)                     continue                 board[i][j] = "B"                 for x in [1, -1, 0]:                     for y in [1, -1, 0]:                         if x == 0 and y == 0: continue                         nxt_i, nxt_j = i + x, j + y                         if nxt_i < 0 or nxt_i >= row or nxt_j < 0 or nxt_j >= col: continue                         if board[nxt_i][nxt_j] == "E":                             queue.append((nxt_i, nxt_j))                             board[nxt_i][nxt_j] = "B"  # 主要是用于标识该点已经被访问过，防止后续重复的添加相同的‘E’点         bfs(i, j)         return board

关于本篇文章大家有任何建议或意见，欢迎在评论区留言交流！

觉得不错的小伙伴，感谢点赞、关注加收藏哦！

欢迎关注下方GZH：阿旭算法与机器学习，共同学习交流~