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, val0, leftNone, rightNone): 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总结广度优先搜索是一种重要的图论算法它可以用于遍历树和图以及解决许多相关问题如最短路径查找、连通性判断等。通过队列的方式广度优先搜索可以按照距离根节点的远近顺序进行遍历。广度优先搜索的核心思想是先访问所有相邻节点然后再访问这些相邻节点的相邻节点以此类推按照距离根节点的远近顺序进行遍历。掌握广度优先搜索的原理和实现对于理解和解决图论相关问题非常重要。