FA2-BFS层序遍历-邻接表

代码实现

/**
 * 图的广度优先搜索遍历（BFS）- 邻接表实现
 * 
 * 算法思想：
 * 1. 从起始顶点开始，先访问该顶点
 * 2. 然后依次访问该顶点的所有未被访问的邻接顶点
 * 3. 再按这些邻接顶点被访问的顺序，依次访问它们的未被访问的邻接顶点
 * 4. 重复此过程直到所有顶点都被访问
 * 
 * 核心数据结构：
 * - visit[]: 访问标记数组，防止重复访问
 * - que[]: 循环队列，存储待访问的顶点
 * - front, rear: 队列的头尾指针
 */

void BFS(ALGraph G, int v) { //v为起点
    // 访问标记数组，初始化为0（未访问）
    // visit[i] = 1表示顶点i已被访问，visit[i] = 0表示未访问
    int visit[G->vexnum] = {0};

    // 循环队列，用于存储待访问的顶点
    // BFS的特点是先进先出（FIFO），所以使用队列
    int que[G->vexnum];

    // 队列指针初始化
    // front: 队头指针，指向队列第一个元素的前一个位置
    // rear: 队尾指针，指向队列最后一个元素的位置
    int front = 0, rear = 0;

    // 标记起始顶点v为已访问
    visit[v] = 1;
    // 将起始顶点v入队
    que[++rear] = v;

    // 当队列不为空时继续循环
    // 队列为空表示所有可达的顶点都已访问完毕
    while (front != rear) {
        // 出队操作：取出队头元素
        v = que[++front];

        // 访问当前顶点（这里简化为打印顶点编号）
        printf("%d ", v);

        // 遍历当前顶点的所有邻接顶点
        // p指向当前顶点的第一条边
        ArcNode* p = G.adjlist[v].firstarc;

        // 遍历该顶点的所有邻接边
        for (; p != NULL; p = p->nextarc) {
            // 检查邻接顶点是否已被访问
            if (visit[p->adjvex] == 0) {
                // 标记邻接顶点为已访问
                visit[p->adjvex] = 1;
                // 将未访问的邻接顶点入队
                que[++rear] = p->adjvex;
            }
        }
    }
}

复杂度分析

时间复杂度：O(V + E)

• V: 顶点数，E: 边数
• 每个顶点最多入队和出队一次：O(V)
• 每条边最多被检查一次：O(E)
• 总时间复杂度：O(V + E)

空间复杂度：O(V)

• visit[]数组：O(V)
• que[]队列：O(V)
• 总空间复杂度：O(V)

图解说明

示例图结构（邻接表表示）：
0 -> 1 -> 2
1 -> 0 -> 3
2 -> 0 -> 3
3 -> 1 -> 2 -> 4
4 -> 3

BFS执行过程（从顶点0开始）：

步骤1：访问0
队列：[0]
visit: [1,0,0,0,0]

步骤2：访问0的邻接点1,2
队列：[1,2]
visit: [1,1,1,0,0]

步骤3：访问1的邻接点3（0已访问）
队列：[2,3]
visit: [1,1,1,1,0]

步骤4：访问2的邻接点3（0已访问，3已访问）
队列：[3]
visit: [1,1,1,1,0]

步骤5：访问3的邻接点4（1,2已访问）
队列：[4]
visit: [1,1,1,1,1]

步骤6：访问4的邻接点3（已访问）
队列：[]
visit: [1,1,1,1,1]

访问顺序：0 -> 1 -> 2 -> 3 -> 4

相关知识点延伸

1. BFS与DFS的区别

• BFS: 广度优先，层序遍历，使用队列，适合找最短路径
• DFS: 深度优先，纵深遍历，使用栈（递归），适合拓扑排序

2. 队列实现的优化建议

// 更规范的循环队列入队出队操作
// 入队
rear = (rear + 1) % maxsize;
que[rear] = vertex;

// 出队
front = (front + 1) % maxsize;
vertex = que[front];

3. BFS的应用场景

• 最短路径问题：无权图中两点间的最短路径
• 连通性检测：判断图是否连通
• 二分图判断：通过BFS给节点着色
• 拓扑排序：有向无环图的层次遍历

4. 改进建议

• 使用动态内存分配避免固定大小限制
• 添加返回值表示遍历结果
• 可以扩展为带权图的最短路径算法（Dijkstra）