LeetCode 广度优先搜索（BFS）题解

LeetCode 广度优先搜索（BFS）题解

题目描述

广度优先搜索是一种用于遍历或搜索树或图的算法。该算法从根节点开始，先访问所有相邻节点，然后再访问这些相邻节点的相邻节点，以此类推，按照距离根节点的远近顺序进行遍历。

示例：

对于以下树结构：

1 / \ 2 3 / \ 4 5

广度优先搜索的遍历顺序可以是：1 → 2 → 3 → 4 → 5。

解题思路

方法：广度优先搜索

思路：

• 广度优先搜索的核心思想是按照距离根节点的远近顺序进行遍历，先访问所有相邻节点，然后再访问这些相邻节点的相邻节点。
• 对于树结构，广度优先搜索通常使用队列来实现，先将根节点入队，然后依次出队并将其相邻节点入队。
• 对于图结构，广度优先搜索同样需要使用队列，并记录已访问的节点，以避免重复访问。

复杂度分析：

• 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。每个顶点和边都会被访问一次。
• 空间复杂度：O(V)，需要使用队列来存储待访问的节点，最坏情况下队列的大小为 V。

代码实现

方法：广度优先搜索（树的层序遍历）

# 定义树节点 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # 广度优先搜索（层序遍历） def bfs_level_order(root): if not root: return [] result = [] queue = [root] while queue: level_size = len(queue) level = [] for _ in range(level_size): node = queue.pop(0) level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result # 测试 def test_bfs_level_order(): # 构建树结构 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) # 测试层序遍历 print(bfs_level_order(root)) # 输出：[[1], [2, 3], [4, 5]] if __name__ == "__main__": test_bfs_level_order()

方法：广度优先搜索（图的遍历）

from collections import deque # 广度优先搜索（图的遍历） def bfs_graph(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: node = queue.popleft() print(node, end=' ') for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # 测试 def test_bfs_graph(): # 构建图结构 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } # 测试图的遍历 print("BFS traversal starting from A:") bfs_graph(graph, 'A') # 输出：A B C D E F if __name__ == "__main__": test_bfs_graph()

测试用例

测试用例 1：树的层序遍历

输入：

1 / \ 2 3 / \ 4 5

输出：[[1], [2, 3], [4, 5]]

测试用例 2：图的遍历

输入：

A -- B -- D | | C -- F -- E

输出：A B C D E F

总结

广度优先搜索是一种重要的图论算法，它可以用于遍历树和图，以及解决许多相关问题，如最短路径查找、连通性判断等。通过队列的方式，广度优先搜索可以按照距离根节点的远近顺序进行遍历。

广度优先搜索的核心思想是：先访问所有相邻节点，然后再访问这些相邻节点的相邻节点，以此类推，按照距离根节点的远近顺序进行遍历。

掌握广度优先搜索的原理和实现，对于理解和解决图论相关问题非常重要。