面试题：C++ 实现简单图的广度优先搜索

Question

假设有一个简单的无向图，节点用整数表示，用邻接表存储。请用C++ 编写一个函数实现对该图的广度优先搜索，并输出从指定起始节点开始访问节点的顺序。例如，给定图节点集合为{1, 2, 3, 4}，边为{(1, 2), (1, 3), (2, 4)}，起始节点为1，输出应为1 2 3 4。

Answer 1

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

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

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";

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

你可以这样调用这个函数：

int main() {
    // 假设节点从0开始编号，邻接表存储图
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3},
        {0},
        {1}
    };
    int start = 0;
    BFS(graph, start);
    return 0;
}

在上述代码中：

1. BFS 函数实现了广度优先搜索。它接受一个用邻接表表示的图 graph 和起始节点 start。
2. 使用一个布尔数组 visited 记录节点是否被访问过。
3. 使用一个队列 q 来实现层次遍历。
4. 首先将起始节点标记为已访问并放入队列，然后在队列不为空时，取出队首节点，输出它，并将其未访问的邻居节点标记为已访问并入队。
5. 在 main 函数中构建了一个简单的图，并调用 BFS 函数从指定起始节点开始进行广度优先搜索。