🧮 广度优先搜索 (Breadth-First Search (BFS))

难度 / Difficulty: 中等 (Medium)
分类 / Category: 图遍历 (Graph Traversal)
时间复杂度 / Time Complexity: O(V + E)
空间复杂度 / Space Complexity: O(V)

📖 算法简介 / Introduction

广度优先搜索是一种层次遍历算法，先访问所有邻居节点，再向外扩展。

BFS is a level-order traversal algorithm that visits all neighbor nodes first before expanding outward.

💡 算法原理 / Principle

使用队列，从起点开始，先访问所有邻居入队，再依次处理队列中的节点。

Using a queue, start from source, enqueue all neighbors, then process nodes in queue order.

📝 代码实现 / Implementation

from collections import deque

def bfs(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)
    return visited

✨ 示例 / Example

在Graph {‘A’: [‘B’, ‘C’], ‘B’: [‘D’, ‘E’], ‘C’: [‘F’], ‘D’: [], ‘E’: [‘F’], ‘F’: []} 中从A开始层次遍历。

Level-order traversing graph from node A in {‘A’: [‘B’, ‘C’], ‘B’: [‘D’, ‘E’], ‘C’: [‘F’], ‘D’: [], ‘E’: [‘F’], ‘F’: []}.

🎯 适用场景 / Scenarios

最短路径, 层次遍历, 社交网络好友推荐

Shortest path, Level-order traversal, Social network friend recommendations

🔄 扩展阅读 / Further Reading

• 建议在 LeetCode 或 HackerRank 上刷相关题目
• 尝试自己实现非递归版本
• 对比其他同类型算法的性能差异