邻接表的广度优先算法使用链表方式实现

邻接表的广度优先算法可以使用链表方式实现，具体实现方法与使用 vector 的方式类似，只是在遍历邻居节点时需要遍历链表。以下是使用链表实现的 C++ 代码示例：

#include <iostream>
#include <queue>

using namespace std;

// 邻接表节点定义
struct AdjListNode {
    int dest; // 目标节点
    struct AdjListNode* next; // 指向下一个节点的指针
};

// 邻接表定义
struct AdjList {
    struct AdjListNode* head; // 指向链表头的指针
};

// 图定义
class Graph {
private:
    int V; // 图的顶点数
    struct AdjList* adj; // 指向邻接表的指针
public:
    Graph(int V); // 构造函数
    void addEdge(int src, int dest); // 添加边
    void BFS(int start); // 广度优先遍历
};

Graph::Graph(int V) {
    this->V = V;
    adj = new AdjList[V];
    for (int i = 0; i < V; ++i) {
        adj[i].head = NULL;
    }
}

void Graph::addEdge(int src, int dest) {
    // 添加从 src 到 dest 的边
    struct AdjListNode* newNode = new AdjListNode;
    newNode->dest = dest;
    newNode->next = adj[src].head;
    adj[src].head = newNode;

    // 添加从 dest 到 src 的边（无向图）
    newNode = new AdjListNode;
    newNode->dest = src;
    newNode->next = adj[dest].head;
    adj[dest].head = newNode;
}

void Graph::BFS(int start) {
    bool* visited = new bool[V];
    for (int i = 0; i < V; ++i) {
        visited[i] = false;
    }

    queue<int> q;
    q.push(start);
    visited[start] = true;

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

        struct AdjListNode* node = adj[cur].head;
        while (node != NULL) {
            int neighbor = node->dest;
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
            node = node->next;
        }
    }
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.BFS(0);
    return 0;
}

输出结果为：0 1 2 3，表示从节点 0 开始，依次遍历了节点 1、2、3。