FA3-BFS层序遍历-邻接矩阵

代码实现

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

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

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

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

    // 将起始顶点v入队
    que[++rear] = v;
    // 标记起始顶点v为已访问（可在入队前或入队后标记）
    visit[v] = 1;

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

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

        // 遍历所有顶点，查找当前顶点的邻接顶点
        for (int i = 0; i < G.numver; i++) {
            // 检查是否存在从顶点v到顶点i的边，且顶点i未被访问
            if (G.Edge[v][i] == 1 && visit[i] == 0) {
                // 将未访问的邻接顶点入队
                que[++rear] = i;
                // 标记邻接顶点为已访问（防止重复入队）
                visit[i] = 1;
            }
        }
    }
}

复杂度分析

时间复杂度：O(V²)

• V: 顶点数
• 外层while循环最多执行V次（每个顶点出队一次）
• 内层for循环每次执行V次（遍历所有顶点查找邻接点）
• 总时间复杂度：O(V × V) = O(V²)

空间复杂度：O(V)

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

图解说明

示例图的邻接矩阵表示：
    0 1 2 3 4
  0 0 1 1 0 0
  1 1 0 0 1 0
  2 1 0 0 1 0
  3 0 1 1 0 1
  4 0 0 0 1 0

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

步骤1：访问0，查找邻接点
G.Edge[0][0]=0 ❌  G.Edge[0][1]=1 ✅  G.Edge[0][2]=1 ✅  
G.Edge[0][3]=0 ❌  G.Edge[0][4]=0 ❌
队列：[0] → 出队0 → 队列：[] → 入队1,2 → 队列：[1,2]
visit: [1,1,1,0,0]

步骤2：访问1，查找邻接点
G.Edge[1][0]=1 ❌(已访问)  G.Edge[1][1]=0 ❌  G.Edge[1][2]=0 ❌  
G.Edge[1][3]=1 ✅  G.Edge[1][4]=0 ❌
队列：[1,2] → 出队1 → 队列：[2] → 入队3 → 队列：[2,3]
visit: [1,1,1,1,0]

步骤3：访问2，查找邻接点
G.Edge[2][0]=1 ❌(已访问)  G.Edge[2][1]=0 ❌  G.Edge[2][2]=0 ❌  
G.Edge[2][3]=1 ❌(已访问)  G.Edge[2][4]=0 ❌
队列：[2,3] → 出队2 → 队列：[3] → 无新增 → 队列：[3]
visit: [1,1,1,1,0]

步骤4：访问3，查找邻接点
G.Edge[3][0]=0 ❌  G.Edge[3][1]=1 ❌(已访问)  G.Edge[3][2]=1 ❌(已访问)  
G.Edge[3][3]=0 ❌  G.Edge[3][4]=1 ✅
队列：[3] → 出队3 → 队列：[] → 入队4 → 队列：[4]
visit: [1,1,1,1,1]

步骤5：访问4，查找邻接点
队列：[4] → 出队4 → 队列：[] → 无新增
visit: [1,1,1,1,1]

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

相关知识点延伸

1. 邻接表与邻接矩阵的比较

特性	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V+E)
判断边存在	O(1)	O(degree)
找邻接点	O(V)	O(degree)
适用场景	稠密图	稀疏图

2. BFS算法优化建议

// 改进版本：避免重复入队
for (int i = 0; i < G.numver; i++) {
    if (G.Edge[v][i] == 1 && visit[i] == 0) {
        visit[i] = 1;  // 立即标记，防止重复入队
        que[++rear] = i;
    }
}

3. 循环队列的规范实现

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front, rear;
} Queue;

// 入队操作
void enqueue(Queue *q, int x) {
    if ((q->rear + 1) % MAXSIZE == q->front) return; // 队满
    q->rear = (q->rear + 1) % MAXSIZE;
    q->data[q->rear] = x;
}

// 出队操作
int dequeue(Queue *q) {
    if (q->front == q->rear) return -1; // 队空
    q->front = (q->front + 1) % MAXSIZE;
    return q->data[q->front];
}

4. BFS的重要应用

• 最短路径：在无权图中求两点间最短路径
• 连通分量：找出图中所有连通分量
• 二分图检测：通过BFS进行二分图判断
• 网络爬虫：网页链接的层次遍历
• 社交网络分析：好友关系的层次扩展

5. 与用户代码的区别说明

原代码中的语法错误已修正： - G.Edge[v][i] 1 → G.Edge[v][i] == 1 - visit[i] 0 → visit[i] == 0 - visit[i] = 1; 的位置调整到正确的循环内部

review