C++中如何实现广度优先搜索_BFS算法实现与性能优化

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

using namespace std;

void bfs(const vector<vector<int>>& graph, int startNode) {
    int numNodes = graph.size();
    vector<bool> visited(numNodes, false);
    queue<int> q;

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

    while (!q.empty()) {
        int currentNode = q.front();
        q.pop();
        cout << "Visiting node: " << currentNode << endl;

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

int main() {
    // 示例图的邻接表表示
    vector<vector<int>> graph = {
        {1, 2},   // Node 0 的邻居
        {0, 3, 4}, // Node 1 的邻居
        {0, 5},   // Node 2 的邻居
        {1},      // Node 3 的邻居
        {1},      // Node 4 的邻居
        {2}       // Node 5 的邻居
    };

    bfs(graph, 0); // 从节点 0 开始 BFS

    return 0;
}

// 在上面的代码示例中，`visited` 向量就是用来解决环路问题的。
// 每次将邻居节点加入队列前，都会检查 `visited[neighbor]` 是否为 `false`。