考研笔记

板子：BFS 求无权图单源最短路

无权图（或者所有边的权值都相同）的单源最短路：BFS 按距离一层一层往外扩，第一次到达某个顶点时，走的就是最短路。

代码

void BFS_MinDistance(MGraph &G, int u, int d[], int path[]) {   // u 到各顶点的最短路径长度（边数）
    int q[MAXV], front = 0, rear = 0;
    for (int i = 0; i < G.numVertices; i++) {
        d[i] = -1;                           // -1 表示还没到达，同时充当 visited
        path[i] = -1;                        // path[i]：最短路上 i 的前一个顶点
    }
    d[u] = 0;
    q[rear++] = u;
    while (front < rear) {
        int v = q[front++];
        for (int w = 0; w < G.numVertices; w++)
            if (G.Edge[v][w] != 0 && d[w] == -1) {   // 第一次到达 w：这就是最短距离
                d[w] = d[v] + 1;             // 比 v 远一步
                path[w] = v;                 // 记下 w 是从 v 过来的
                q[rear++] = w;
            }
    }
}
 
void printPath(int path[], int v) {          // 输出从起点到 v 的路径（按从前往后的顺序）
    if (path[v] != -1) printPath(path, path[v]);   // 先把前面那一段输出
    printf("%d ", v);
}

复杂度：邻接矩阵时间 ，邻接表时间 ；空间 。

关键边界

位置为什么
第一次到达就定下 d[w]BFS 按距离 0、1、2……一层层出队，先到达的一定是更短的路，后面不用再更新
d[i] = -1 兼作 visited教材用 d[i] = ∞ 再加一个 visited[]，这里合成一个数组
path 存前驱顺着 path 只能从终点倒着走回起点。要正着输出就用递归，或者先存下来再倒序输出
d[v] 仍是 从 到不了 ，这时不要调用 printPath

易错点

  • 带权图不能用 BFS 求最短路：边数少的路不一定权值小，要用 Dijkstra。
  • 如果题目只问「距离 不超过 的顶点」，按层处理（每轮记下队列长度）就行，不需要 d[]，写法见 层序遍历与按层处理。

链接

反向链接