题46

题46

题目

[!error]+
Q:【2023 统考真题】已知无向连通图 中各边的权值均为 1. 在下列算法中,一定能够求出图 中从某顶点到其余各顶点最短路径的是 ( ).
I. Prim 算法
II. Kruskal 算法
III. 图的广度优先搜索算法
A. 仅 I
B. 仅 III
C. 仅 I、II
D. I、II、III

分析

[!NOTE]+
A:注意区分，最小生成树和最短路径的区别，prim算法求最小生成树-aw和kruskal算法求最小生成树-aw都是求最小生成树的算法，不是求最短路径的算法，而图的广度优先搜索可以求最短路径
prim算法求最小生成树-aw也就是加点法，每次都是选当前未点亮的点里面，边最小的；kruskal算法求最小生成树-aw也就是加边法，每次再连上权重最小的那两个点的边，是并查集的应用，因为我们把点看作集合

解

[!done]+
B
Prim 算法和 Kruskal 算法用于求解最小生成树, 最小生成树中某顶点到其余各顶点的路径不一定具有最短路径的性质。例如,在下图所求得的最小生成树中, 到 的路径长度为 2,但原图中 到 的最短路径长度为 1 。

图的广度优先搜索算法总按距离由近到远来遍历图中的每个顶点, 因此可用来求解非带权图 (或各边权值均相同) 的单源最短路径问题。