一个具有10个顶点的连通无向图,其所有边的权重均不相同。在使用克鲁斯卡尔算法求其最小生成树的过程中,已经选择了6条边,此时若图中存在一个包含4个顶点的连通分量,则该连通分量中已选取的边的数目是多少?

答案解析

克鲁斯卡尔算法是贪心策略,不关心整体的连通性,只关心当前选取的边不构成回路。已经选择的6条边在图中形成了若干个连通分量。题中提到存在一个包含4个顶点的连通分量,该分量内部的边是逐渐被添加的。因为连通分量是联通的,所以最少0条,最多是 4-1=3条,否则形成回路。因此,该连通分量内部已经选择的边数可以在0到3之间。选项A只涵盖了0和1,选项B只涵盖了1和2,选项C只涵盖了2和3,均不完整。只有选项D包含了所有的可能取值,因此是正确答案。
正确答案:D
随机推荐
开始刷题