Python - 深夜数据结构与算法之 BFS & DFS_python的bfs\dfs算法

目录

一.引言

二.BFS 与 DFS 简介

1.Search 搜索

2.DFS 深度优先

3.BFS 广度优先

4.DFS & BFS

三.经典算法实战

1.Generate-Parentheses [22]

2.Level-Order-Travesal [102]

3.Word-Ladder [127]

4.Num-Of-Islands [200]

5.Min-Gene-Mutation [433]

6.Largest-Values [515]

7.Mine-Clearance [529]

四.总结

---

一.引言

BFS 广度优先搜索与 DFS 深度优先搜索是树以及网格等相关题目最常见的方法之一，其通过不同的遍历方式对分叉结构进行遍历，对于树、图而言，其可以是二叉、多叉，其可以是上下左右，下面让我们深入了解下 BFS 与 DFS。

二.BFS 与 DFS 简介

1.Search 搜索

不论是 BFS 还是 DFS，它们都是数据结构节点的访问方式，为了效率足够高，我们希望每个节点访问且仅访问一次，因而衍生出了 DFS - Depth First Search 深度优先搜索与 BFS - Breadth First Search 广度优先搜索两种遍历方式。除此之外还有按照节点优先级访问的算法，不过需要特定的场景才会使用。 

2.DFS 深度优先

深度优先搜索，我们前面提到的二叉树的前中后序遍历都是深度优先搜索的一种，对于二叉树而言，其深度搜索的路径是向 Left 左子树和 Right 右子树递进，多叉树的话则是其 Children 节点集合，对于图而言，则是其他相邻的点 V，其通式可以参照下面的写法。

◆ 递归写法

◆ 非递归写法

 ◆ 树的遍历

◆ 图的遍历 

3.BFS 广度优先

广度优先与深度优先不同，其从每一层下探访问节点，就好比是一滴水波纹逐渐向下扩散，然后扩散到每一层的节点上。

◆ 树的遍历 

◆ 代码写法

这里的队列其实就是我们常用到的列表。注意这里的 queue pop 是先进先出的，大家要和上面的 stack.pop 区分开。

4.DFS & BFS

我们可以根据上面的图再理解下 DFS 与 BFS 的遍历方式，如果都是用 List 实现的话，BFS 是 Deque 先进先出，DFS 则是 Stack 后进先出。

三.经典算法实战

1.Generate-Parentheses [22]

括号生成: https://leetcode.cn/problems/generate-parentheses/description/

◆ 题目分析

这里可以看做是一颗二叉树，其每个节点可以分叉为 '(' 和 ')'，我们需要遍历生成情况，并判断当前生成是否有效，再向下遍历。有效的条件有两个，一个是左括号一定是开头的第一个字符，另一个是左括号要和右括号数量一致。

◆ 广度优先

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        res = []
 
        def dfs(cur, left, right):
            # 终止条件
            if left == n and right == n:
                res.append(cur)
            
            # 左括号要在前面
            if left < n:
                bfs(cur + "(", left + 1, right)
            # 右括号要比左括号小
            if right < left:
                bfs(cur + ")", left, right + 1)
        
        dfs("", 0, 0)
        return res

 DFS 遍历的模版，直接一层一层下去找，直到满足 2n 的条件。

◆ 栈实现

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        res = []
 
        queue = [("", 0, 0)]
 
        while queue:
            cur, left, right = queue.pop(0)
 
            if left == right == n:
                res.append(cur)
            
            if left < n:
                queue.append((cur + "(", left + 1, right))
            if right < left:
                queue.append((cur + ")", left, right + 1))
        
        return res

DFS、BFS 的几种模版一定要多多练习，手到擒来。

◆ 二刷留念

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        # 保存结果
        result = []
 
        def generate(left, right, cur):
            # Stop
            if left == n and right == n:
                result.append(cur)
 
            if left < n:
                generate(left + 1, right, cur + "(")
            
            if right < left:
                generate(left, right + 1, cur + ")")
 
        generate(0, 0, "")
 
        return result

使用 DFS，不使用栈实现。 

2.Level-Order-Travesal [102]

二叉树层序遍历: https://leetcode.cn/problems/binary-tree-level-order-traversal

◆ 题目分析

二叉树 BFS 遍历，这里要求我们逐层按列表返回而不是一个列表全部返回，所以我们在 BFS 套模版的基础上，还需要记录其 level 层的位置。

◆ 广度优先

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        
        # 先进先出
        queue = [(0, root)]
        res = []
 
        while queue:
            # 记录对应的层次
            index, cur = queue.pop(0)
 
            if len(res) < index + 1:
                res.append([])
            res[index].append(cur.val)
 
            # 添加层消息与节点
            if cur.left:
                queue.append((index + 1, cur.left))
            if cur.right:
                queue.append((index + 1, cur.right))
            
        return res

按层遍历，每层下探时增加 index 找到其在 res 中对应的 list 保存即可。 

◆ 深度优先

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
 
        def dfs(root, level):
            if not root:
                return 
 
            if len(res) == level:
                res.append([])
            res[level].append(root.val)
            
            # 通过 level 存储层的信息
            if root.left:
                dfs(root.left, level + 1) 
            if root.right:
                dfs(root.right, level + 1)   
        
        dfs(root, 0)
        return res

层序遍历适合本题，但是深度遍历也可以实现，我们在向下探索的过程中可以获取当前的 level，只需将遍历到的结果对应的 level 找到即可。 

◆ 二刷留念

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
 
        res = {}
 
        stack = [(root, 0)]
 
        while stack:
            node, level = stack.pop(0)
            if level not in res:
                res[level] = []
            res[level].append(node.val)
 
            if node.left:
                stack.append((node.left, level + 1))
            if node.right:
                stack.append((node.right, level + 1))
 
        return res.values()

3.Word-Ladder [127]

单词接龙: https://leetcode.cn/problems/word-ladder/description/

◆ 题目分析

层序遍历的方法，类似前面的基因突变，这里可以理解为连续突变且每次可以突变 26 个字母。

◆ 广度优先

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        # 去重使用
        valid_word = set(wordList)
        
        if endWord not in wordList or len(wordList) == 0:
            return 0
        
        queue = [(beginWord, 1)]
 
        while queue:
 
            new_queue = []
 
            for word, step in queue:
                # 停止条件
                if word == endWord:
                    return step
                
                # 处理当前元素
                for i in range(len(word)):
                    # 突变每一个位置
                    for char in 'abcdefghijklmnopqrstuvwxyz':
                        # 去重优化
                        if char != word[i]:
                            new_word = word[:i] + char + word[i + 1:] 
                            if new_word in valid_word:
                                valid_word.remove(new_word)
                                new_queue.append((new_word, step + 1))
            queue = new_queue
        return 0

这里 for char in 'abcd...' 可以使用 orc + chr 转换:

    for char in range(ord('a'), ord('z') + 1):
        print(chr(char))

◆ 双向 BFS

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        # 去重使用
        valid_word = set(wordList)
        
        if endWord not in wordList or len(wordList) == 0:
            return 0
        
        # 双向 BFS
        begin, end, step = {beginWord}, {endWord}, 1
 
        while begin and end:
 
            if len(begin) > len(end):
                begin, end = end, begin
 
            # 存储下一层
            next_level = set()
            for word in begin:
                for i in range(len(word)):
                    # a-z
                    for x in 'abcdefghijklmnopqrstuvwxyz':
                        # 节省无必要的替换
                        if x != word[i]:
                            new_word = word[:i] + x + word[i + 1:]
 
                            if new_word in end:
                                return step + 1
                            if new_word in valid_word:
                                next_level.add(new_word)
                                valid_word.remove(new_word)
            begin = next_level
            step += 1
 
        return 0

为了加快搜素速度我们改写为双向 BFS，Begin-A-B-C-D-End 我们拆分为 Begin -> B，End -> B，两边同时检索，最终输出总的 step。这里我们尝试了 ord 的写法，但是时间复杂度没有上面的直接。

4.Num-Of-Islands [200]

岛屿数量: https://leetcode.cn/problems/number-of-islands/description/

◆ 题目分析

对于每个点 row col，其都有上下左右 4 个分叉点，我们可以作为四叉树遍历，通过 generate_related_nodes 方法生成其不同分叉，并判断是否可以联通 [row,col] == 1，最后遍历所有 gird 的点，看可以走通多少次返回 count 即可。

◆ 深度优先

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # 异常情况
        if not grid:
            return 0
 
        # 记录岛屿数量
        numLand = 0
 
        # 遍历并标记
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == "1":
                    self.dfs(row, col, grid)
                    numLand += 1
        
        return numLand
    
    # 在网格索引范围内
    def inArea(self, row, col, grid):
        return 0 <= row < len(grid) and 0 <= col < len(grid[0])
    
    def dfs(self, row, col, grid):
        # 判断节点合法性
        if not self.inArea(row, col, grid) or grid[row][col] != "1":
            return
 
        grid[row][col] = "2"
 
        self.dfs(row + 1, col, grid)
        self.dfs(row, col + 1, grid)
        self.dfs(row - 1, col, grid)
        self.dfs(row, col - 1, grid)

继续 dfs 的条件是在 grid 内且值为 "1"。 

5.Min-Gene-Mutation [433]

最小基因变化: https://leetcode.cn/problems/minimum-genetic-mutation/

◆ 题目分析

题目给定了基因的 4 种类型 'ACGT'，就像是 4 叉树一样，我们每次遍历有 4 个方向可以走，当前层遍历完再向下一个索引继续遍历，总共有 4^^8 种情况，由于有 bank 的限制，我们可以过滤掉多种情况。 

◆ 广度优先

class Solution(object):
    def minMutation(self, startGene, endGene, bank):
        """
        :type startGene: str
        :type endGene: str
        :type bank: List[str]
        :rtype: int
        """
 
        # 没有基因库或最终突变不在基因库
        if not bank or endGene not in bank:
            return -1
 
        queue = []
        queue.append((startGene, 0))
        # 记录基因是否有效
        valid_bank = set(bank)
 
        while queue:
            # 获取当前步数
            gene, step = queue.pop(0)
 
            # 突变每一个位置
            for i in range(len(gene)):
                for g in 'ACGT':
                    # 从第一个位置开始，每个突变一次
                    if g != gene[i]:
                        change_gene = gene[:i] + g + gene[i + 1:]
                        if change_gene == endGene:
                            return step + 1
                        elif change_gene in valid_bank:
                            queue.append((change_gene, step + 1))
                            valid_bank.remove(change_gene)
 
        return -1
 

 判断 g != gene[i] 减少相同字符的替换。

6.Largest-Values [515]

每层的最大值: https://leetcode.cn/problems/find-largest-value-in-each-tree-row/

◆ 题目分析

层序遍历，找到每一层的最大值即可，也可以深度遍历，记录即可。

◆ 广度优先

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        
        if not root:
            return []
 
        queue = [root]
        res = []
 
        while queue:
            cur_max = -99999999999
            new_queue = []
            # 遍历每一层
            for i in range(len(queue)):
                if queue[i]:
                    cur_max = max(cur_max, queue[i].val)
                    if queue[i].left:
                        new_queue.append(queue[i].left)
                    if queue[i].right:
                        new_queue.append(queue[i].right)
            res.append(cur_max)
            queue = new_queue
        
        return res
                

空间复杂度主要使用了 queue，其余操作主要在计算 max。 

◆ 深度优先

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        
        res = []
 
        def dfs(root, level):
            # 停止条件
            if not root:
                return
            
            # 当前层逻辑
            if len(res) == level:
                res.append(-9999999999)
            res[level] = max(res[level], root.val)
 
            # 下一层
            if root.left:
                dfs(root.left, level + 1)
            if root.right:
                dfs(root.right, level + 1)
        
        dfs(root, 0)
        return res

同理，DFS 时可以使用 level 保存层的信息，我们通过 level 与数组建立关系构造 max 即可。

7.Mine-Clearance [529]

扫雷游戏: https://leetcode.cn/problems/minesweeper/description/ 

◆ 题目分析

给定初始二维数组和起点，返回修改后的二维数组。若起点处是雷，即 ‘M’，直接将其修改为 'X'，游戏结束；若起点处是空，即 ‘E’，则从起点开始向 8 邻域中的空地搜索，直到到达邻接