FC06-求不带权的无向图或有向图中，顶点v到其他各顶点的最短路径长度（以边数计），并将结果存储到数组dist中¶

代码实现¶

C
// 函数 BFS：使用广度优先搜索求不带权图中从顶点 v 到其他各顶点的最短路径
// 参数：
// G - 图的邻接表表示
// v - 起始顶点
// dist[] - 存储最短路径长度的数组
void BFS(Graph G, int v, int dist[]) {
    // 初始化访问标记数组，0 表示未访问，1 表示已访问
    int visit[maxsize] = {0};

    // 初始化距离数组，所有距离设为无穷大（INT16_MAX）
    for (int i = 0; i < G.numver; i++) {
        dist[i] = INT16_MAX;
    }

    // 初始化队列，用于 BFS 遍历
    int que[maxsize];           // 队列数组
    int front = 0, rear = 0;    // 队列的头指针和尾指针

    // 初始化起始顶点
    visit[v] = 1;               // 标记起始顶点为已访问
    dist[v] = 0;                // 起始顶点到自身的距离为 0
    que[++rear] = v;            // 将起始顶点入队

    // BFS 主循环
    while (front != rear) {     // 当队列不为空时继续循环
        v = que[++front];       // 出队一个顶点

        // 遍历当前顶点的所有邻接顶点
        Node p = G.adjlist[v].firstarc;  // 获取第一个邻接边
        for (; p != NULL; p = p->nextarc) {  // 遍历所有邻接边
            // 如果邻接顶点未被访问过
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;           // 标记为已访问
                que[++rear] = p->adjvex;        // 将邻接顶点入队
                // 更新最短距离：邻接顶点的距离 = 当前顶点距离 + 1
                dist[p->adjvex] = dist[v] + 1;
            }
        }
    }
}

代码逻辑解析¶

1. BFS 算法原理¶

广度优先搜索按照距离起始顶点的层次逐层扩展
在不带权图中，BFS 能够找到从起始顶点到其他各顶点的最短路径
因为每一层的顶点到起始顶点的距离都相同

2. 算法步骤¶

初始化阶段：
将所有顶点标记为未访问
将所有距离初始化为无穷大
将起始顶点的距离设为 0 并入队
BFS 遍历阶段：
从队列中取出一个顶点
遍历该顶点的所有邻接顶点
对于未访问的邻接顶点，更新其距离并入队
距离更新规则：
邻接顶点的距离 = 当前顶点的距离 + 1

3. 队列操作¶

入队：que[++rear] = vertex
出队：vertex = que[++front]
队空判断：front == rear

时间复杂度分析¶

1. 顶点访问¶

每个顶点最多被访问一次
时间复杂度：O(V)，其中 V 是顶点数

2. 边的处理¶

每条边最多被检查一次
时间复杂度：O(E)，其中 E 是边数

3. 总体时间复杂度¶

O(V + E) - 线性时间复杂度

空间复杂度分析¶

1. 额外数组空间¶

visit[] 数组：O(V)
dist[] 数组：O(V)（作为参数传入，不计入额外空间）
que[] 队列：O(V)

2. 其他变量¶

常量级别的局部变量：O(1)

3. 总体空间复杂度¶

O(V)

较难理解部分的说明¶

1. 为什么 BFS 能求最短路径？¶

层次遍历特性：¶

Text Only
1 2 3 4 5 6 7	`起始顶点 v (距离 0) ↓ 距离 1 的顶点集合 ↓ 距离 2 的顶点集合 ↓ ...`

由于 BFS 按层次扩展，第一次访问某个顶点时就得到了最短距离。

图解说明：¶

假设无向图如下：

Text Only
1 2 3	`A --- B --- D \| \| \| C --- E --- F`

从顶点 A 开始的 BFS 过程：

Text Only
1 2 3 4	`第0层: A (距离 0) 第1层: B, C (距离 1) 第2层: D, E (距离 2) 第3层: F (距离 3)`

2. 队列操作细节¶

C
// 队列实现细节
int que[maxsize];    // 循环队列数组
int front = 0;       // 队头指针（指向队头元素的前一个位置）
int rear = 0;        // 队尾指针（指向队尾元素）

// 入队操作
que[++rear] = vertex;

// 出队操作  
vertex = que[++front];

// 队空判断
if (front == rear) // 队列为空

延伸知识点¶

1. 改进版本 - 带路径记录¶

C
// 带路径记录的 BFS
void BFSWithPath(Graph G, int v, int dist[], int path[]) {
    int visit[maxsize] = {0};

    for (int i = 0; i < G.numver; i++) {
        dist[i] = INT16_MAX;
        path[i] = -1; // -1 表示无前驱
    }

    int que[maxsize];
    int front = 0, rear = 0;

    visit[v] = 1;
    dist[v] = 0;
    que[++rear] = v;

    while (front != rear) {
        v = que[++front];

        Node p = G.adjlist[v].firstarc;
        for (; p != NULL; p = p->nextarc) {
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;
                que[++rear] = p->adjvex;
                dist[p->adjvex] = dist[v] + 1;
                path[p->adjvex] = v; // 记录前驱顶点
            }
        }
    }
}

// 打印从起始顶点到目标顶点的路径
void printPath(int start, int end, int path[]) {
    if (end == start) {
        printf("%d ", start);
        return;
    }

    if (path[end] == -1) {
        printf("No path from %d to %d\n", start, end);
        return;
    }

    printPath(start, path[end], path);
    printf("%d ", end);
}

2. 循环队列优化¶

C
// 循环队列版本，避免队列溢出
void BFS_CircularQueue(Graph G, int v, int dist[]) {
    int visit[maxsize] = {0};

    for (int i = 0; i < G.numver; i++) {
        dist[i] = INT16_MAX;
    }

    int que[maxsize];
    int front = 0, rear = 0;

    visit[v] = 1;
    dist[v] = 0;
    que[rear] = v;
    rear = (rear + 1) % maxsize; // 循环队列入队

    while (front != rear) {
        v = que[front];
        front = (front + 1) % maxsize; // 循环队列出队

        Node p = G.adjlist[v].firstarc;
        for (; p != NULL; p = p->nextarc) {
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;
                que[rear] = p->adjvex;
                rear = (rear + 1) % maxsize;
                dist[p->adjvex] = dist[v] + 1;
            }
        }
    }
}

3. Dijkstra 算法对比（带权图）¶

C
// Dijkstra 算法（适用于带权图）
void Dijkstra(Graph G, int v, int dist[]) {
    int visited[maxsize] = {0};

    for (int i = 0; i < G.numver; i++) {
        dist[i] = INT16_MAX;
    }

    dist[v] = 0;

    for (int i = 0; i < G.numver; i++) {
        // 找到未访问顶点中距离最小的
        int minDist = INT16_MAX, u = -1;
        for (int j = 0; j < G.numver; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }

        if (u == -1) break; // 所有顶点都已处理
        visited[u] = 1;

        // 更新 u 的邻接顶点的距离
        Node p = G.adjlist[u].firstarc;
        for (; p != NULL; p = p->nextarc) {
            int newDist = dist[u] + p->weight;
            if (newDist < dist[p->adjvex]) {
                dist[p->adjvex] = newDist;
            }
        }
    }
}

4. 实际应用场景¶

社交网络：计算两个人之间的最短关系链
网络路由：在无权网络中找到最短跳数路径
游戏开发：NPC 寻路算法
地图导航：在等权道路网络中计算最短路径
病毒传播分析：分析信息在网络中的传播速度

5. 性能优化技巧¶

C
// 提前终止优化版本
void BFS_Optimized(Graph G, int v, int dist[], int target) {
    int visit[maxsize] = {0};

    for (int i = 0; i < G.numver; i++) {
        dist[i] = INT16_MAX;
    }

    int que[maxsize];
    int front = 0, rear = 0;

    visit[v] = 1;
    dist[v] = 0;
    que[++rear] = v;

    while (front != rear) {
        v = que[++front];

        // 如果找到了目标顶点，可以提前终止
        if (v == target) {
            return;
        }

        Node p = G.adjlist[v].firstarc;
        for (; p != NULL; p = p->nextarc) {
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;
                que[++rear] = p->adjvex;
                dist[p->adjvex] = dist[v] + 1;
            }
        }
    }
}

这种方法体现了图遍历和最短路径的经典思想，BFS 是解决无权图最短路径问题的标准算法，具有重要的理论和实用价值。