求下面带权图的最小(代价)生成树时,可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是()。
A. (V1,V3)
B.(V1,V4)
C.(V2,V3)
D.(V3,V4)
方法一:模拟 + 枚举 + 取差集...
用户登录可进行刷题及查看答案
方法一:模拟 + 枚举 + 取差集
Kruskal算法:首先将边从图中剥离然后按照边权值从小到大排序。然后从小到大依次将边复原到图中,插入后检查是否成环,如果成环,丢弃插入的边,重复上述过程直到有顶点都连通。
Kruskal过程模拟如下图所示:
登录后提交答案
暂无评论,来抢沙发