C++怎么实现广度优先搜索(BFS)_C++图的遍历与队列应用

vector<vector<int>> graph = {
    {1, 2},      // 节点0连接1和2
    {0, 3, 4},   // 节点1连接0、3、4
    {0, 5},      // 节点2连接0、5
    {1},         // 节点3连接1
    {1},         // 节点4连接1
    {2}          // 节点5连接2
};

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

void bfs(const vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);  // 标记访问状态
    queue<int> q;

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

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

        // 遍历u的所有邻接节点
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

// 示例调用
int main() {
    vector<vector<int>> graph = {{1,2}, {0,3,4}, {0,5}, {1}, {1}, {2}};
    cout << "BFS traversal: ";
    bfs(graph, 0);
    return 0;
}

0 1 2 3 4 5

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

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

    while (!q.empty()) {
        int size = q.size();  // 当前层的节点数
        cout << "Level " << level << ": ";

        while (size--) {
            int u = q.front();
            q.pop();
            cout << u << " ";

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

Level 0: 0 
Level 1: 1 2 
Level 2: 3 4 5