17370845950

图的广度优先搜索从起始顶点开始逐层遍历，使用队列和访问标记数组避免重复访问；C++中常用邻接表vector结合queue实现，示例构建5个顶点的图并从0开始BFS，输出0 1 2 3 4；适用于最短路径、连通分量等场景，稀疏图推荐邻接表，可扩展parent数组记录路径。

图的广度优先搜索（BFS）是一种用于遍历或搜索图的算法，它从起始顶点开始，逐层访问其邻接节点，使用队列保证访问顺序。在C++中，可以通过邻接表或邻接矩阵结合标准库queue来高效实现。

图的表示方式：邻接表

通常使用vector>表示邻接表，每个索引对应一个顶点，存储与其相连的顶点列表。

示例：

假设有5个顶点，边为 (0,1), (0,2), (1,3), (1,4)，邻接表构造如下：

vector> graph(5);
graph[0] = {1, 2};
graph[1] = {3, 4};
// 其他默认为空

BFS核心逻辑与实现步骤

BFS的关键是使用队列和访问标记数组，避免重复访问节点。

步骤说明：

• 创建布尔数组visited记录每个顶点是否已访问
• 创建队列，将起始顶点入队并标记为已访问
• 当队列非空时，取出队首顶点并访问
• 将其所有未访问的邻接顶点入队并标记
• 循环直到队列为空

C++实现代码：

#include 
#include 
#include 
using namespace std;

void bfs(const vector>& graph, int start) {
    int n = graph.size();
    vector visited(n, false);
    queue q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 访问当前节点

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

完整可运行示例

以下是一个完整的程序，构建图并执行BFS：

int main() {
    vector> graph(5);
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0};
    graph[3] = {1};
    graph[4] = {1};

    cout << "BFS traversal: ";
    bfs(graph, 0);
    return 0;
}

输出：
0 1 2 3 4

注意事项与优化建议

BFS适用于无权图的最短路径问题，也可扩展用于层级遍历、连通分量判断等场景。

• 确保图的顶点编号从0开始连续，否则需用map管理visited状态
• 若需记录路径，可额外维护parent数组，在入队时记录前驱节点
• 对于稀疏图，邻接表比邻接矩阵更节省空间
• 注意处理孤立节点或非连通图的情况，可能需要多次调用BFS

基本上就这些。BFS结构清晰，配合STL容器写起来简洁高效。