GESP 2026年6月 C++八级单选题第9题

Question

某无向带权图有边 (1,2,4)、(1,3,2)、(2,3,1)、(2,4,5)、(3,4,8)、(3,5,10)、(4,5,2)。该图最小生成树的总权值为( )。

Accepted Answer

答案：D。Kruskal 从小到大选边不成环:选 (2,3,1)、(1,3,2)、(4,5,2),再选能连通两部分的 (2,4,5),四条边连通 5 个点,总权 1+2+2+5=10,选 D。 最小生成树 = 用最小的总权把所有点连通、且不成环(n 个点选 n−1 条边)。

GESP 2026年6月 C++八级 单选题 第9题