🏷️ 知识点：广度优先搜索

已知无向连通图 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。

下列关于图的叙述中，正确的是（ ）。

图的概念

A. 有向图必定存在入度为 0 的顶点 B. 有向无环图的拓扑排序有序序列存在且唯一 C. 各顶点的度均大于等于 2 的无向图必有回路 D. 可用 BFS 算法求出带权图中每一对顶点的最短路径

[tag_link]

正确答案：C

逐项判断：

• A 错。一个有向环中每个顶点的入度都为 1，因此有向图不一定有入度为 0 的顶点。
• B 错。DAG 一定存在拓扑序，但某一步若有多个零入度候选，选择顺序不同就会产生多个拓扑序。
• C 对。若无向图无环，则每个非空有限森林至少有一个度为 0 或 1 的顶点；反过来，每个顶点度至少为 2 的无向图不可能是森林，必有回路。
• D 错。BFS 只能直接求无权图或各边等权图的单源最短路径，不能求一般带权图的每对最短路径；非负权单源问题可用 Dijkstra，多源问题可用 Floyd。