什么是广度优先搜索？

广度优先搜索（Breadth-First Search，简称BFS） 是一种用于遍历或搜索树或图数据结构的算法。其核心思想是逐层扩展，先访问距离起始节点最近的所有节点，再访问更远的节点。

BFS 的基本思想

1. 从起始节点开始，放入队列
2. 取出队首节点，访问其所有未访问的邻接节点
3. 将这些邻接节点依次入队
4. 重复步骤2-3，直到队列为空

BFS 利用队列这种先进先出（FIFO）的数据结构，确保了按照距离起始节点的远近顺序访问节点。

BFS 与 DFS 的区别

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 邻接表表示的图
vector<vector<int>> adj;
vector<bool> visited;

// BFS 实现
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

// BFS 求最短路径
vector<int> bfs_shortest_path(int start, int target, int n) {
    vector<int> dist(n, -1);
    vector<int> parent(n, -1);
    queue<int> q;
    
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (u == target) break;
        
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    
    // 还原路径
    vector<int> path;
    if (dist[target] == -1) return path;  // 无路径
    
    for (int v = target; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    // 示例图：6个节点
    int n = 6;
    adj.resize(n);
    
    // 添加边 (无向图)
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[1].push_back(4); adj[4].push_back(1);
    adj[2].push_back(5); adj[5].push_back(2);
    
    visited.assign(n, false);
    cout << "BFS (从节点0开始): ";
    bfs(0);
    cout << endl;
    
    // 测试最短路径
    vector<int> path = bfs_shortest_path(0, 4, n);
    cout << "从0到4的最短路径: ";
    for (int v : path) cout << v << " ";
    cout << endl;
    
    return 0;
}

BFS 的应用场景

1. 最短路径搜索：在无权图中找到两点间的最短路径
2. 层次遍历：按层次遍历二叉树或图
3. 社交网络：查找”n度朋友”
4. 迷宫最短路径：找到起点到终点的最少步数
5. 拓扑排序（特殊情况）：按层次输出有序节点

复杂度分析

• 时间复杂度：O(V + E)，V为节点数，E为边数
• 空间复杂度：O(V)，用于存储访问标记和队列

总结

广度优先搜索是寻找最短路径的最佳选择。BFS层层扩展的特性使其特别适合处理”最近优先”类问题。掌握BFS对于理解更复杂的算法（如Dijkstra、A*等）也有很大帮助。