给予邻接表的广度优先遍历 c++

在C++中，使用邻接表（Adjacency List）进行广度优先遍历(Breadth-First Search, BFS)通常适用于图数据结构，因为邻接列表更利于存储无向图或稀疏图，其中每个节点只有一小部分相邻节点。

BFS的基本步骤如下：

1. **初始化队列**：将起始节点入队，并标记该节点已访问。
2. **循环处理**：
- 取出队首节点，如果它是目标节点，则返回成功。
- 将该节点的所有未访问的邻居（即它们对应的边）加入到队列中，并标记它们为已访问。
3. **递归终止**：如果没有找到目标节点并且队列为空，表示图中不存在从起始节点到达目标节点的路径。

以下是一个简单的C++示例，假设`adjList`是一个邻接表表示的图，`visit`用于记录节点状态：

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

// 假设邻接表的节点包含一个vector作为邻接节点集合
struct Node {
    int value;
    vector<int> adj;
};

bool bfs(Node* start, int target, vector<Node*>& adjList) {
    queue<Node*> q;
    Node* current = nullptr;
    start->visit = true; // 标记开始节点已访问

    q.push(start);

    while (!q.empty()) {
        current = q.front();
        q.pop();

        if (current->value == target) return true; // 找到了目标节点

        for (int neighbor : current->adj) {
            if (!adjList[neighbor]->visit) { // 邻居未访问
                adjList[neighbor]->visit = true;
                q.push(adjList[neighbor]);
            }
        }
    }

    return false; // 没有找到路径
}

int main() {
    // 初始化你的邻接表...
    Node start = {0, {1, 2}}; // 起始节点及其相邻节点
    Node end = {5, {}}; // 目标节点
    vector<Node*> adjList = {/*...*/};
    
    if (bfs(&start, end.value, adjList)) {
        cout << "找到了从起点到终点的路径!" << endl;
    } else {
        cout << "无法从起点到达终点." << endl;
    }
    return 0;
}