这段代码使用 C++ 实现了一个基于邻接表存储结构的有向图，并提供了图的创建、打印和广度优先遍历（BFS） 功能。

核心数据结构代码定义了三种结构体来构建邻接表：

全局数组 int visited[MAX] 用于在 BFS 遍历时标记顶点是否已被访问。

主要函数解析

1. Creat(GraAdList& G)：创建邻接表

此函数通过用户输入构建图 。

1. 输入顶点数和边数。
2. 依次输入每个顶点的数据（char类型），并初始化其邻接表头指针为 NULL。
3. 依次输入每条边。对于边 (i, j)，代码采用头插法创建一个新的边节点，并将其插入到顶点 i 的邻接表头部 。这表示一条从顶点 i 指向顶点 j 的有向边。

2. myprint(GraAdList G)：打印邻接表

此函数以可视化格式输出图的邻接表结构，便于检查图的构建是否正确 。
*对于每个顶点，先打印其数据，然后遍历其邻接链表，打印所有邻接顶点的下标。

3. BFS(GraAdList G, int v)：广度优先遍历

这是代码的核心算法，从顶点 v 开始对图进行广度优先遍历 。
1.使用一个数组 queue[MAX] 模拟队列，并维护 front 和 rear 指针。
2. 访问起始顶点 v，将其标记为已访问并入队。
3. 当队列不为空时：
* 队头顶点 v 出队。
* 遍历顶点 v 的所有邻接顶点：
* 如果某个邻接顶点 j 未被访问，则访问它、标记已访问、并将其入队。
4. 此过程会逐层访问所有从起始顶点可达的顶点。

4. main() 函数

程序的执行流程：

1. 声明图 G 并调用 Creat(G) 创建图。
2. 调用 myprint(G) 打印邻接表。
3. 初始化 visited 数组为 0（未访问）。
4. 调用 BFS(G, 0) 从下标为 0 的顶点开始进行广度优先遍历，并输出遍历序列。

代码示例与关键步骤

以下是 BFS 函数中队列操作和邻接点遍历的核心逻辑：

// 使用数组模拟队列
int queue[MAX];
front = rear = -1;
// 顶点v入队
queue[++rear] = v;

while (front != rear) { // 队列不为空
    v = queue[++front]; // 顶点出队
    p = G.AdList[v].first; // 获取该顶点的第一条边 while (p) { // 遍历所有邻接点
        j = p->adjvex; // 邻接点下标
        if (visited[j] == 0) {
            // 访问、标记、入队 cout << G.AdList[j].data << " ";
            visited[j] = 1;
            queue[++rear] = j;
        }
        p = p->next; // 指向下一个邻接点
    }
}

总结

该程序完整演示了邻接表这一图的存储结构，以及在其上进行的广度优先搜索（BFS） 算法。BFS 借助队列实现，其特点是按“距离”起始顶点的层次逐层遍历，常用于寻找最短路径或系统性的探索 。需要注意的是，此代码构建的是有向图，且 BFS 函数只能遍历从起始顶点出发能够到达的顶点（连通分量）。

参考来源

• 数据结构学习笔记（C++）：邻接表实现图的存储结构(广度优先遍历详解)
• 用邻接表存储有向图并实现DFS（递归+非递归）BFS（非递归）两种遍历
• 图---邻接表(建立，深度遍历，广度遍历)
• 图的BFS广度优先搜索
• 图的基本操作（基于邻接表）：图的构造，深搜（DFS），广搜（BFS）