题目

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

I. 普里姆（Prim）算法

II. 克鲁斯卡尔（Kruskal）算法

III. 图的广度优先搜索

错因

A

把"最小生成树"和"最短路径"混为一谈。Prim 算法保证生成的树是全局边权和最小的连通无环子图，但不保证从根到任意叶子的路径在原图中是最短的——树里的路径可能绕路。即使所有边权都是 1，构造出的 MST 也只是一棵覆盖所有点的生成树，其中两点的路径长度（边数）不必等于原图最短路径长度。

C

误以为 MST 类算法（Prim、Kruskal）天然解决最短路径。Kruskal 同 Prim：它保证总权和最小，不保证两点间路径最短。在权值均为 1 的图里，最小生成树就是任意一棵生成树（边数都是 ），但这棵树的"任意两点距离"不等于"图上的最短距离"。

D

把三个算法都当对，就是 A + C 两个错误的合集——既混淆了 MST 与最短路径，又默认 BFS 在等权图能做最短路径（这点确实对）。一个正确加两个错误，整体错。

总解析

核心区别：

算法	解决的问题	在等权图上的特殊性
Prim	最小生成树（MST）	退化成"任意一棵生成树"
Kruskal	最小生成树（MST）	同上
BFS	等权图的单源最短路径	按层扩展即最短路径树

为什么 BFS 能求等权最短路径：BFS 从源点 出发按层扩展——第 层的所有顶点到 恰好需要 条边。在所有边权 = 1 的图里"最少边数"就等于"最短路径长度"，所以 BFS 给出的距离就是真正的最短距离。

为什么 Prim/Kruskal 不行：MST 关心的是"所有边权和最小且连通无环"，与"两点间路径"无关。简单反例——四点环 A–B–C–D–A，所有边权 1：

• BFS 从 A：A→B 距离 1，A→C 距离 2，A→D 距离 1。
• Prim/Kruskal 出来的 MST 可能是路径 A–B–C–D，从 A 到 D 在树里要走 3 步，但原图里只要 1 步。

最终答案是 B（仅 III）。

格式调整说明：原骨架题干末尾有一行 ![](/practice/exam-images/2023-06.jpg) 的图片引用，但 2023-06.assets/ 不存在该文件，且本题文字描述完整、不需要配图，已删除该引用。