邻接表用顶点数组和链表实现图，BFS借助队列按层访问；顶点节点存数据和首边指针，边节点存目标下标和下一指针；无向图双向建边，有向图单向建边；BFS需visited数组防重入，非连通图需多次启动。

用邻接表实现图结构并执行广度优先搜索（BFS），关键在于两步：一是合理组织顶点与边的链式关系，二是借助队列按层推进访问。整个过程不依赖全局矩阵，空间效率高，特别适合稀疏图。

邻接表的基本结构设计

邻接表由一个顶点数组和若干单链表组成。每个顶点对应数组中的一个元素，该元素包含顶点数据和指向其邻接边链表的指针。

• 顶点节点（VertexNode）存数据（如字符或编号）和首条邻接边指针（firstEdge）
• 边节点（EdgeNode）存目标顶点下标（adjvex）和指向下一邻接边的指针（next）
• 图类（如 ALGraph）维护顶点数、边数及顶点数组，初始化时将所有 firstEdge 设为 nullptr

构建邻接表的具体操作

输入顶点列表和边对后，逐条插入边。对无向图，需双向添加；对有向图，只按方向添加一次。

• 为每条边 (u, v) 创建新边节点，adjvex = v，插入到 u 的边链表头部（或尾部，视实现而定）
• 若为无向图，再创建边节点 adjvex = u，插入到 v 的边链表中
• 插入时注意避免重复边（可选检查），边数 edgeNum 随之递增

广度优先搜索的实现要点

BFS 核心是“先来后到”，用队列管理待访问顶点，并用布尔数组标记已访问状态，防止重复入队。

• 初始化：将起始顶点 v 入队，设 visited[v] = true
• 循环处理：只要队列非空，就取出队首顶点 u，打印或记录；遍历 u 的所有邻接点 w（通过 u 的边链表）
• 对每个 w，若 visited[w] == false，则设为 true 并入队
• 使用标准 queue<int> 或手动实现循环队列均可，重点是 FIFO 行为

代码层面的关键细节

实际编码时容易忽略但影响正确性的几点：

• 顶点下标从 0 开始统一管理，避免因输入字符（如 'A'）未映射导致越界
• 边链表插入推荐头插法，时间复杂度 O(1)；若需保持邻接点顺序（如按编号升序），则改用尾插并维护尾指针
• visited 数组大小必须 ≥ 顶点总数，且每次 BFS 前需重置（除非单次运行）
• 对于非连通图，需在外层遍历所有未访问顶点，分别启动 BFS，才能完成全图遍历