BFS广度优先搜索是一种图遍历算法使用队列作为核心数据结构遵循“先入先出”FIFO原则。其典型应用场景包括在无权图中求解单源最短路径即边数最少的路径因为BFS按层扩展首次到达某节点时即为最短距离二叉树或图的层次遍历逐层访问从根/起点开始一层一层向外扩散还可用于判断图的连通性、求解最小操作步数问题如迷宫最短出路、单词接龙等。实现要点初始化队列将起点入队并标记已访问循环出队访问其所有未访问邻接点入队并标记通常配合visited集合/数组避免重复访问若需记录路径或距离可额外维护distance[]或parent[]数组。fromcollectionsimportdequedefbfs(graph,start):visitedset()queuedeque([start])visited.add(start)distance{start:0}whilequeue:nodequeue.popleft()forneighboringraph.get(node,[]):ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)distance[neighbor]distance[node]1returndistanceBFS广度优先搜索与DFS深度优先搜索在时间复杂度和空间复杂度上的异同如下✅相同点时间复杂度均为 O(V E)V 为顶点数E 为边数因为两者在最坏情况下都需要访问图中所有顶点和边邻接表表示下若用邻接矩阵存储时间复杂度均为 O(V²)因需检查每对顶点是否连通。❌不同点关键差异在于空间复杂度及实际行为维度BFSDFS辅助数据结构队列FIFO栈递归调用栈 或 显式栈空间复杂度O(W)W 为图的最大层宽即某一层最多节点数→ 最坏情况如星形图或完全图可达 O(V)O(H)H 为图的最大搜索深度即最长路径长度→ 最坏情况如链状图可达 O(V)但实际常更省空间尤其稀疏图/树典型空间表现在宽而浅的图中空间开销大如社交网络“六度人脉”早期层节点爆炸在深而窄的图中空间开销大如单链、树高较大时递归栈深 补充说明DFS 递归实现的空间复杂度包含函数调用栈深度易受栈溢出影响需注意语言栈限制迭代DFS可显式控制栈但逻辑稍复杂。BFS 的队列在层次遍历时天然支持“按层处理”便于实现最短路径、最小步数等DFS 更适合回溯、拓扑排序、连通分量Tarjan、路径存在性判断等。
BFS广度优先搜索是一种图遍历算法使用队列作为核心数据结构遵循“先入先出”FIFO原则。其典型应用场景包括在无权图中求解单源最短路径即边数最少的路径因为BFS按层扩展首次到达某节点时即为最短距离二叉树或图的层次遍历逐层访问从根/起点开始一层一层向外扩散还可用于判断图的连通性、求解最小操作步数问题如迷宫最短出路、单词接龙等。实现要点初始化队列将起点入队并标记已访问循环出队访问其所有未访问邻接点入队并标记通常配合visited集合/数组避免重复访问若需记录路径或距离可额外维护distance[]或parent[]数组。fromcollectionsimportdequedefbfs(graph,start):visitedset()queuedeque([start])visited.add(start)distance{start:0}whilequeue:nodequeue.popleft()forneighboringraph.get(node,[]):ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)distance[neighbor]distance[node]1returndistanceBFS广度优先搜索与DFS深度优先搜索在时间复杂度和空间复杂度上的异同如下✅相同点时间复杂度均为 O(V E)V 为顶点数E 为边数因为两者在最坏情况下都需要访问图中所有顶点和边邻接表表示下若用邻接矩阵存储时间复杂度均为 O(V²)因需检查每对顶点是否连通。❌不同点关键差异在于空间复杂度及实际行为维度BFSDFS辅助数据结构队列FIFO栈递归调用栈 或 显式栈空间复杂度O(W)W 为图的最大层宽即某一层最多节点数→ 最坏情况如星形图或完全图可达 O(V)O(H)H 为图的最大搜索深度即最长路径长度→ 最坏情况如链状图可达 O(V)但实际常更省空间尤其稀疏图/树典型空间表现在宽而浅的图中空间开销大如社交网络“六度人脉”早期层节点爆炸在深而窄的图中空间开销大如单链、树高较大时递归栈深 补充说明DFS 递归实现的空间复杂度包含函数调用栈深度易受栈溢出影响需注意语言栈限制迭代DFS可显式控制栈但逻辑稍复杂。BFS 的队列在层次遍历时天然支持“按层处理”便于实现最短路径、最小步数等DFS 更适合回溯、拓扑排序、连通分量Tarjan、路径存在性判断等。
