🏷️ 知识点：单源最短路径

已知无向连通图 G 中各边的权值均为 1，下列算法中，一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是（ ）。

I. 普利姆算法

II. 克鲁斯卡尔算法

III. 图的广度优先搜索

最小生成树

A. 仅 I B. 仅 III C. 仅 I、II D. I、II、III

[tag_link]

正确答案：B

各边权值都为 1 时，路径权值就等于经过的边数。BFS 从源点按层扩展，BFS 的层数就是边数，所以某顶点第一次被发现时得到的就是从源点到它的最短路径，III 正确。Prim 和 Kruskal 的目标是最小化整棵生成树的总权值，不是同时最小化某个源点到各顶点的距离，I、II 均不保证成立。因此仅 III 正确，选 B。