vlambda博客
学习文章列表

【原创教程】数据结构与算法（5）——广度与深度优先搜索


一、广度优先搜索

广度优先搜索（BFS，Breadth First Search） 的一个常见应用是找出从根结点到目标结点的最短路径，其实现用到了队列。下面用一个例子来说明BFS的原理，在下图中，我们BFS 来找出根结点 A 和目标结点 G 之间的最短路径。

【原创教程】数据结构与算法（5）——广度与深度优先搜索

图3：BFS例子


  • 首先初始化一个队列Q，将根节点入队：A

  • A出队，将与A相邻的节点入队，此时队列为BCD

  • B出队，将与B相邻的节点入队，此时队列为CDE

  • C出队，将与C相邻的节点入队，此时队列为DEF（节点E已经被遍历过，不需要再入队）

  • D出队，将与D相邻的节点入队，此时队列为EFG

  • E出队，下面没有节点

  • F出队，下面是G，已遍历过，为目标值，遍历结束

BFS代码模板：

def BFS(graph, start, end):
	queue = []
	queue.append([start])
	visited.add(start)	# 对于图来说，要标记节点已经被访问过，防止重复访问
	
	while queue:
		node = queue.pop()	# 出队
		visited.add(node)	# 标记访问
		
		process(node)	# 对节点进行一些处理
		nodes = generate_related_nodes(node)	# 得到当前节点的后继节点，并且没有被访问过
		queue.push(nodes)
	# 其他处理部分
	...

二、深度优先搜索

与 BFS 类似，深度优先搜索（DFS，Depth-First-Search） 也可用于查找从根结点到目标结点的路径。下面通过一个例子，用DFS 找出从根结点 A 到目标结点 G 的路径。

【原创教程】数据结构与算法（5）——广度与深度优先搜索

图3：BFS例子


在上面的例子中，我们从根结点 A 开始。首先，我们选择结点 B的路径，并进行回溯，直到我们到达结点 E，我们无法更进一步深入。然后我们回溯到A并选择第二条路径到结点 C。从 C 开始，我们尝试第一条路径到 E 但是 E已被访问过。所以我们回到 C 并尝试从另一条路径到 F。最后，我们找到了 G。虽然我们成功找出了路径 A-> C-> F-> G ，但这不是从 A 到 G 的最短路径。

DFS代码模板：

# 递归写法
visited = set()
def DFS(node, visited):
	visited.add(node)
	# process current node here
	...
	for next_node in node.children():
		if next_node not in visited:
			DFS(next_node, visited)

三、例题

（1）岛屿数量问题

此题为leetcode的第200题（https://leetcode-cn.com/problems/number-of-islands/）。有两个思路：

  • Flood fill 算法： 深度优先搜索或广度优先搜索

  • 并查集

Flood fill 算法的含义：是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典 算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在 GNU Go 和 扫雷 中，Flood Fill算法被用来计算需要被清除的区域。

对于这类问题，其实就是从一个点开始，遍历与这个起点连着的格子，遍历过的格子就标上“被访问过”的记号，找到与之相连的所有格子后，就是发现了一个岛屿。而这个遍历的过程可以用广度优先或深度优先实现，具体讲解可以参考：https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/，动画很明白，这里只贴上代码：

# 广度优先搜索
from typing import List
from collections import deque

class Solution:
    # x-1,y
    # x,y-1 x, y x,y+1
    # x+1,y
    # 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]

    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        marked = [[False for _ in range(n)] for _ in range(m)]
        count = 0
        # 从第 1 行、第 1 格开始，对每一格尝试进行一次 DFS 操作
        for i in range(m):
            for j in range(n):
                # 只要是陆地，且没有被访问过的，就可以使用 BFS 发现与之相连的陆地，并进行标记
                if not marked[i][j] and grid[i][j] == '1':
                    # count 可以理解为连通分量，你可以在广度优先遍历完成以后，再计数，
                    # 即这行代码放在【位置 1】也是可以的
                    count += 1
                    queue = deque()
                    queue.append((i, j))
                    # 注意：这里要标记上已经访问过
                    marked[i][j] = True
                    while queue:
                        cur_x, cur_y = queue.popleft()
                        # 得到 4 个方向的坐标
                        for direction in self.directions:
                            new_i = cur_x + direction[0]
                            new_j = cur_y + direction[1]
                            # 如果不越界、没有被访问过、并且还要是陆地，就入队
                            if 0 <= new_i < m and 0 <= new_j < n and not marked[new_i][new_j] and grid[new_i][new_j] == '1':
                                queue.append((new_i, new_j))
                                # 入队后马上要标记为“被访问过”
                                marked[new_i][new_j] = True
                    #【位置 1】
        return count
# 深度优先搜索
from typing import List

class Solution:
    # x-1,y
    # x,y-1 x,y x,y+1
    # x+1,y
    # 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]

    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        marked = [[False for _ in range(n)] for _ in range(m)]
        count = 0
        # 从第 1 行、第 1 格开始，对每一格尝试进行一次 DFS 操作
        for i in range(m):
            for j in range(n):
                # 只要是陆地，且没有被访问过的，就可以使用 DFS 发现与之相连的陆地，并进行标记
                if not marked[i][j] and grid[i][j] == '1':
                    # 连通分量计数
                    count += 1
                    # DFS搜索
                    self.__dfs(grid, i, j, m, n, marked)
        return count
	
	# 递归进行深度优先搜索
    def __dfs(self, grid, i, j, m, n, marked):
        marked[i][j] = True
        for direction in self.directions:
            new_i = i + direction[0]
            new_j = j + direction[1]
            if 0 <= new_i < m and 0 <= new_j < n and not marked[new_i][new_j] and grid[new_i][new_j] == '1':
                self.__dfs(grid, new_i, new_j, m, n, marked)

（2）二叉树的最大深度

此题为leetcode第104题（https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/）
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
深度优先解法：

# 深度优先搜索
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 递归，深度优先搜索
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left)    # 左子树高度
            right_height = self.maxDepth(root.right)  # 右子树高度
            return max(left_height, right_height) + 1


广度优先解法：

# 迭代，广度优先搜索
from collections import deque
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        
        depth = 0
        q = deque()
        q.append((1, root))
        while q:
            curr_depth, node = q.pop()
            depth = max(depth, curr_depth)

            if node.left:
                q.append((curr_depth + 1, node.left))
            if node.right:
                q.append((curr_depth + 1, node.right))
        return depth


（3）二叉树的最小深度

此题为leetcode第111题（https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/）
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
深度优先解法：

# 递归，深度优先搜索
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 递归，深度优先搜索
        if root is None: 
            return 0 
        if root.left is None:   # 若左子树为空，root的深度为1+右子树深度
            return 1 + self.minDepth(root.right)
        if root.right is None:  # 若右子树为空，root的深入为1+左子树深度
            return 1 + self.minDepth(root.left)
        
        left_height = self.minDepth(root.left)    # 左子树高度
        right_height = self.minDepth(root.right)  # 右子树高度
        
        return min(left_height, right_height) + 1


广度优先解法：

# 迭代，广度优先搜索
from collections import deque
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 迭代，广度优先搜索
        if root is None:
            return 0
        
        q = deque()
        q.append((1, root))
        depth = 1
        while q:
            curr_depth, node = q.popleft()
            # 如果node为叶子节点，则此时深度为最小深度
            if node.left is None and node.right is None:
                return curr_depth
            
            if node.left:
                q.append((curr_depth + 1, node.left))
            if node.right:
                q.append((curr_depth + 1, node.right))


（4）括号生成

此题为leetcode第22题（https://leetcode-cn.com/problems/generate-parentheses/）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

# 深度优先搜索加剪枝
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        self.res = []
        self._gen('', 0, 0, n)
        return self.res
    
    def _gen(self, result, left, right, n):
        # left为左括号用了几个，right为右括号用了几个
        if left == n and right == n:
            self.res.append(result)
            return 
        
        # 如果用的左括号小于n个，可以加左括号
        if left < n:
            self._gen(result+'(', left+1, right, n)
        # 只有在用的右括号小于用的左括号时，才可以加右括号
        if right < left:
            self._gen(result+')', left, right+1, n)

（5）N皇后问题

此题为leetcode第51题（https://leetcode-cn.com/problems/n-queens/submissions/）
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n < 1:
            return []
        self.res = []   # 记录最终结果
        self.cols, self.pie, self.na = set(), set(), set()  # 标记横竖、斜角方向
        self.DFS(n, 0, [])
        
        return [['.' * j + 'Q' + '.' * (n - j - 1) for j in col] for col in self.res]
    
    def DFS(self, n, row, curr_state):  # curr_state代表每行的哪些列可以放置皇后，是一种可能的解决方案
        # 如果递归可以走到最后一层，说明curr_state是一种合法的解决方案，将其放入self.res里
        if row >= n:
            self.res.append(curr_state)
            return
        
        # 遍历列
        for col in range(n):
            # 如果当前位置上，可以被横竖、斜角方向上的皇后攻击到，则continue
            if col in self.cols or row + col in self.pie or row - col in self.na:
                continue  
            
            # 如果当前位置不会被攻击到，则标记横竖、斜角方向
            self.cols.add(col)
            self.pie.add(row + col)
            self.na.add(row - col)
            
            # 递归，row+1进入下一行，curr_state+[col]保存一种可能的状态
            self.DFS(n, row + 1, curr_state + [col])
            
            # 上面的递归出来后，清除横竖、斜角方向的标记
            # 因为我们是在(n, col)位置上尝试放置皇后看是否可行
            self.cols.remove(col)
            self.pie.remove(row + col)
            self.na.remove(row - col)

（6）解数独

此题为leetcode第37题（https://leetcode-cn.com/problems/sudoku-solver/submissions/）
编写一个程序，通过已填充的空格来解决数独问题。下面给出最朴素的DFS：

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
 Do not return anything, modify board in-place instead.
 """
        if board is None or len(board) == 0:
            return
        self.solve(board)
    
    def solve(self, board):
        for i in range(len(board)):
            for j in range(len(board)):
                # 循环遍历，找到空位置
                if board[i][j] == '.':
                    # 从1-9遍历
                    for k in range(1, 10):
                        c = str(k)
                        if self.isValid(board, i, j, c):    # 判断c是否可以放在(i, j)上
                            # 如果在(i, j)上放数字c可行的话，先将c放上去
                            board[i][j] = c
                            # 继续递归，看放上c后，后面的是否可行
                            if self.solve(board):
                                return True     # 放上c后可以解决整个数独则返回True
                            else:
                                board[i][j] = '.'   # 不可行的话将c清空
                    return False    # 1-9遍历完后还不行就返回False
        return True    # 可以遍历完整个board就返回True
    
    def isValid(self, board, row, col, c):
        for i in range(9):
            if board[i][col] != '.' and board[i][col] == c:
                return False
            if board[row][i] != '.' and board[row][i] == c:
                return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] != '.' and board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
                return False
        return TrueCopy



（全文完）

作者简介：

李旭东，中科院在读研究生，研究方向为深度学习、工业故障诊断，喜欢读书，希望同各位小伙伴一起交流学习！


个人网站：lixudong.ink

博客：https://blog.csdn.net/u014157632

邮箱：[email protected]


粉丝福利：




往期回顾











推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
16、TCP协议之三次握手 16、TCP协议之三次握手

相关文章