广度优先搜索

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树/图的算法。
它的基本思想是从一个顶点开始，先访问所有相邻节点，然后再按照同样的顺序访问相邻节点的相邻节点。

基本概念

BFS 的工作原理类似于水波纹扩散：

1. 从起点开始，向四周扩散
2. 访问所有距离为1的节点
3. 再访问所有距离为2的节点
4. 以此类推，直到访问完所有可达节点
5. 保证先访问距离近的节点，后访问距离远的节点

实现方式

BFS 主要使用队列来实现，基本步骤：

1. 将起始节点放入队列
2. 取出队首节点访问
3. 将其未访问的相邻节点加入队列
4. 重复步骤2-3直到队列为空

基本实现

void bfs(int start, vector<vector<int>>& graph) {
    queue<int> q;
    set<int> visited;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << "访问节点: " << node << endl;
        
        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

public void bfs(int start, List<List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println("访问节点: " + node);
        
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

def bfs(graph, start):
    queue = deque([start])
    visited = {start}
    
    while queue:
        node = queue.popleft()
        print(f"访问节点: {node}")
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

应用场景

BFS 在很多实际问题中都有应用：

1. 寻找最短路径
2. 计算网络节点间的最小距离
3. 社交网络中的好友推荐
4. 网页爬虫
5. 二叉树的层序遍历

示例：最短路径问题

vector<int> find_shortest_path(vector<vector<int>>& graph, int start, int end) {
    queue<int> q;
    set<int> visited;
    vector<int> parent(graph.size(), -1);
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        if (node == end) {
            vector<int> path;
            for (int cur = end; cur != -1; cur = parent[cur]) {
                path.push_back(cur);
            }
            reverse(path.begin(), path.end());
            return path;
        }
        
        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                parent[neighbor] = node;
                q.push(neighbor);
            }
        }
    }
    return vector<int>();
}

public List<Integer> findShortestPath(List<List<Integer>> graph, int start, int end) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    int[] parent = new int[graph.size()];
    Arrays.fill(parent, -1);
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        
        if (node == end) {
            List<Integer> path = new ArrayList<>();
            for (int cur = end; cur != -1; cur = parent[cur]) {
                path.add(0, cur);
            }
            return path;
        }
        
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                parent[neighbor] = node;
                queue.offer(neighbor);
            }
        }
    }
    return new ArrayList<>();
}

def find_shortest_path(graph, start, end):
    queue = deque([start])
    visited = {start}
    parent = {start: None}
    
    while queue:
        node = queue.popleft()
        
        if node == end:
            path = []
            current = end
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    
    return []

时间复杂度

• 邻接矩阵表示的图：，其中 是顶点数
• 邻接表表示的图：，其中 是顶点数， 是边数

空间复杂度

• ，其中 是顶点数（队列和访问集合的大小）

BFS vs DFS

1. BFS 总是先访问距离起点近的节点，而 DFS 会一直往深处访问
2. BFS 能找到最短路径，DFS 不保证
3. BFS 需要存储所有同层节点，可能占用更多内存
4. BFS 适合找最短路径，DFS 适合搜索全部方案

注意事项

1. 需要注意内存使用（队列可能会很大）
2. 确保正确处理访问标记
3. 对于大图要注意性能问题
4. 需要考虑是否真的需要最短路径

练习建议

1. 实现二叉树的层序遍历
2. 解决迷宫最短路径问题
3. 实现无权图的最短路径查找
4. 尝试在实际问题中应用BFS

经典例题

1. 走迷宫
2. 智能机器人