图的广度优先遍历pta邻接表

以下是使用邻接表表示图的广度优先遍历的C++代码：

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

const int MAXN = 1005;       // 最大顶点数
vector<int> adj[MAXN];      // 邻接表
bool visited[MAXN];         // 标记数组，记录每个顶点是否被访问过

void BFS(int s) {
    queue<int> q;           // 定义队列
    visited[s] = true;      // 标记起点已被访问
    q.push(s);              // 将起点加入队列
    while (!q.empty()) {    // 当队列不为空时循环
        int u = q.front();  // 取出队首元素
        q.pop();            // 弹出队首元素
        cout << u << " ";   // 访问该顶点
        for (int i = 0; i < adj[u].size(); i++) { // 遍历u的所有邻接点
            int v = adj[u][i];
            if (!visited[v]) {  // 如果v未被访问过
                visited[v] = true;  // 标记v已被访问
                q.push(v);          // 将v加入队列
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;          // 输入顶点数和边数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;      // 输入一条边的两个顶点
        adj[u].push_back(v);  // 将v加入u的邻接表
        adj[v].push_back(u);  // 将u加入v的邻接表
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {  // 如果i未被访问过
            BFS(i);         // 从i开始进行BFS遍历
        }
    }
    return 0;
}

其中，`adj`是邻接表，表示每个顶点的所有邻接点；`visited`是标记数组，记录每个顶点是否被访问过；`BFS`函数是广度优先遍历的实现，从起点`s`开始对图进行遍历。在遍历过程中，将访问到的顶点标记为已访问，并将其加入队列中，再依次访问其所有邻接点。最后，遍历完所有连通块之后，即可得到整个图的广度优先遍历序列。