给定一个无向连通图G,其中包含7个顶点和12条边,各边权重互不相同。若使用克鲁斯卡尔算法求解该图的最小生成树,当算法执行过程中已选取权重最小的5条边后,此时图G中可能存在的连通分量个数最多为多少?
答案解析
克鲁斯卡尔算法每次选取当前权重最小且不形成环的边加入最小生成树。初始状态下,每个顶点都视为独立的连通分量,因此7个顶点有7个连通分量。每加入一条边,如果该边的两个端点分别属于不同的连通分量,那么这两个连通分量会合并成一个,使得连通分量个数减1。选取5条边,最多会合并5个连通分量。如果这5条边都是连接不同的连通分量的,那么连通分量个数会减少5个,所以最多剩余7 - 5 = 2个连通分量。需要注意的是,即使选取了最小的5条边,它们也有可能在不同阶段被加入,但连通分量的变化不会超过这个最大值。选项A,1个连通分量表示所有点已经连通,意味着至少选择了6条边;选项C和D大于可能的最大值2。因此,正确答案是B。
正确答案:B