使用Prim算法生成最小生成树[1]的过程是()。A. 从顶点开始,每次选择连接当前树和非树顶点的最小权边B. 每次选择图中权值最小的边,且不形成环C. 基于广度优先遍历D. 基于动态规划

Prim算法用于生成图的最小生成树，其核心思路是从顶点出发，逐步扩展生成树。每次选择连接当前生成树与非生成树顶点的最小权边，确保最终生成树总权重最小。
关键点：

1. 顶点驱动：从任意顶点开始，逐步添加顶点。
2. 局部最优：每一步选择当前最小边，保证全局最优。
3. 避免环路：通过只连接非树顶点，自然避免环路。

选项B描述的是Kruskal算法的特点，而选项C、D与Prim算法无关。

选项分析

选项A

“从顶点开始，每次选择连接当前树和非树顶点的最小权边”

• 正确。Prim算法的核心步骤：初始选择任意顶点，后续每一步在“当前生成树”与“未加入顶点”之间找最小边，将其加入生成树。

选项B

“每次选择图中权值最小的边，且不形成环”

• 错误。这是Kruskal算法的特征。Kruskal按边权排序，依次选择不形成环的最小边，而Prim基于顶点扩展。

选项C

“基于广度优先遍历”

• 错误。广度优先遍历用于图的层序遍历，与最小生成树算法无关。

选项D

“基于动态规划”

• 错误。动态规划用于多阶段决策问题，而Prim是贪心算法的一种。