题库首页 › GESP等级认证(C++) › 题目 25493

在图论算法中,Kruskal算法和Prim算法都可以用来求解最小生成树,且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。( )

A:正确
B:错误

正确答案:正确

答案解析

Kruskal算法通过按边权递增顺序依次选择不构成环的边,逐步连接所有顶点;Prim算法从任意起始顶点出发,每次选择与当前生成树相连且权值最小的边扩展树结构。两种算法均基于贪心策略,每次决策仅依赖当前可选边的最小权值。在任意连通无向图中,若边权唯一确定,则所有最小生成树的总边权和由图的拓扑结构和边权分布共同决定。无论采用何种贪心路径构建,最终生成树的边集可能不同,但其总边权和始终等于该图最小生成树的数学定义所规定的值。算法过程不引入额外约束,故二者求得的总边权和必然一致。

试卷来源:202603 CCF-GESP编程能力等级认证C++八级真题

本卷相关题目

在线做题 同科目题库