单选题 适中
#22010

一个包含8个顶点的完全图(顶点编号1到8),任意两点之间的边权重等于两顶点编号的差的绝对值,该图的最小生成树总权重是多少?

一个包含8个顶点的完全图(顶点编号1到8),任意两点之间的边权重等于两顶点编号的差的绝对值,该图的最小生成树总权重是多少?

未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析

最小生成树是选边构成树且权值和最小。用Kruskal算法,将边权从小到大排序,边权最小的边为(1,2)、(2,3)、(3,4)、(4,5)、(5,6)、(6,7)、(7,8),权值均为1,总和7。