试题-求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第 2 次选中但不是普里姆（Prim）算法（从 V4 开始）第 2 次选中的边是（）。

题目

求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Kruskal）算法第 2 次选中但不是普里姆（Prim）算法（从 V4 开始）第 2 次选中的边是（）。

A.(V1,V3)

B.(V1,V4)

C.(V2,V3)

D.(V3,V4)

解答

正确答案是 C

Kruskal算法是按权值选边，若选边后不形成回路,则保留作为一条边,若形成回路则除去

Prim算法是每次从当前的二叉树节点向外延伸的，选择权值最小的边

克鲁斯卡（Kruskal）算法和普里姆（Prim）算法（从 V4 开始）第1次选中的边都是(v4,v1) 。Kruskal算法第二次可以选择(v1,v3), (v2,v3), (v3,v4); Prim算法第二次可以选择(v1,v3), (v3,v4)

C 3条回复评论

Ciszewski

真的好拼呀

发表于 2022-06-19 23:00:00

墨色槐

资源还可以

发表于 2022-04-21 21:00:00

寒山远火

克鲁斯卡（Kruskal）算法和普里姆（Prim）算法（从 V4 开始）第1次选中的边都是(v4,v1) 。Kruskal算法第二次可以选择(v1,v3),(v2,v3),(v3,v4);Prim算法第二次可以选择(v1,v3),(v2,v3)。原因是Prim算法是每次从当前的二叉树节点向外延伸的

发表于 2018-11-01 15:41:47