2. 考研
  3. 已知无向图G如下所示，使用克鲁斯卡尔(Kruskal)算法求图G的最小生成树，加入到最小生成树中的边依次是( )。

已知无向图G如下所示，使用克鲁斯卡尔(Kruskal)算法求图G的最小生成树，加入到最小生成树中的边依次是( )。

admin2021-03-17  48
问题 已知无向图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)。
转载请注明原文地址:https://www.kaotiyun.com/show/TH3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)