单选题
已知无向图G如下所示,使用克鲁斯卡尔(Kruskal)算法求图G的最小生成树,加入到最小生成树中的边依次是( )。
A、
(b,f),(b,d),(a,e),(c,e),(b,e)
B、
(b,f),(b,d),(b,e),(a,e),(c,e)
C、
(a,e),(b,e),(c,e),(b,d),(b,f)
D、
(a,e),(c,e),(b,e),(b,f),(b,d)
【正确答案】
A
【答案解析】
先将所有边按权值排序,然后依次取权值最小的边但不能在图中形成环,此时取得权值序列为5,6,此时7不能取因为形成了环,接下来取9,10,11,按权值对应的边分别为(b,f),(b,d),(a,e),(c,e),(b,e)。
提交答案
关闭