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

admin2021-03-17 53

问题已知无向图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://kaotiyun.com/show/TH3i777K

计算机408

相关试题推荐

随机试题

最新回复(0)