我要招人

去企业版

首页 > 试题广场 >

求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（Krus

[单选题]

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

```
(V1,V3)
```
```
(V1,V4)
```
```
(V2,V3)
```
```
(V3,V4)
```

推荐

艾晓米Amyfairy

从 V₄ 开始， Kruskal 算法选中的第一条边一定是权值最小的（ V₁,V₄ ）， B 错误。由于 V₁ 和 V₄ 已经可达，第二条边含有 V₁ 和 V₄ 的权值为 8 的一定符合 Prim 算法，排除 A 、 D 。（来自王道论坛）

编辑于 2016-12-01 18:35:01 回复(1)

王道论坛

从 V4 开始， Kruskal 算法选中的第一条边一定是权值最小的（ V1,V4 ）， B 错误。由于 V1 和 V4 已经可达，第二条边含有 V1 和 V4 的权值为 8 的一定符合 Prim 算法，排除 A 、 D 。

发表于 2016-12-13 18:21:33 回复(0)

Shopee内推营业ing

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

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

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

发表于 2017-04-08 16:52:20 回复(0)

__sgf__

Kruskal选边且不构成回路，Prim选点且相连。

发表于 2022-03-14 02:23:27 回复(0)

二咩

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

发表于 2016-11-30 23:19:22 回复(0)

肉丸子fmh

带权图的最小生成树：寻找能过连接所有结点的权值最小的边的集合。（用n-1条边将n个城市用最小的权重连接起来）

prim算法：从任选初始结点出发，寻找当前路径上结点向外联接的所有路径中权值最小的一条。

时间复杂度与结点数有关O(n^2)，与边的数目无关，因此适合稠密图。

kruskal算法：与结点无关，对边按照权值进行排序，每次选择权值最小且不能和集合中其他边构成环路的一条边加入结果集合中，直至找到n-1条边为止。

时间复杂度与边的条数e有关，o(eloge)，与结点数无关，因此适合稀疏图。

发表于 2021-06-25 17:36:44 回复(0)

强连通计算机考研

回顾：

克鲁斯卡尔：以边为核心。

普利姆：以顶点为核心，以子树为核心。

解析：

克鲁斯卡尔：

第一次只会选(1,4)：排除A。

第二次：选(1,3)或(3,4)或(2,3)

普利姆：

第一次选：(1,4)

第二次选：选(1,3)或(3,4)

所以结果是(2,3)

【来自：冯强数据结构考研】

发表于 2020-05-12 14:35:37 回复(0)

狂热的苹果汁

克鲁斯卡尔是每次选取图中最短的边，第一次选边14，长度为5，第二次选长度为8的边，但是有三条，分别是边12 边 23 边 34。普及姆算法就是分为两个集合，第一次选14这条边边，然后在14这两个点集合中选出由这两个点发出的最短边，有边13，边34，那么就只有边23是普里姆没有的了

发表于 2019-12-09 09:47:58 回复(0)

沙月ちゃん

根据Kruskal算法和Prim算法的定义一步步推导。

先看Kruskal算法。

先对边按权值升序排列，得到边权值序列 $\{ 5,8,8,8,10,11 \}$ 。可以看到，第 $2$ 小的权值为 $8$ ，说明Kruskal算法第 $2$ 次选择的边权值是 $8$ 。然而这样的边有三条： $(V_1,V_3),(V_2,V_3),(V_3,V_4)$ 。

这时再看Prim算法：

不妨设集合 $P$ 为已经扩展过的顶点，初始为空。题目要求从 $V_4$ 开始，于是先将 $V_4$ 放入集合 $P$ 中。与集合 $P$ 中所有的顶点相邻的边中，权值最小的边为 $(V_1,V_4)$ ，权值为 $5$ ，于是把顶点 $V_1$ 也放入集合 $P$ 中。接下来，与集合 $P$ 中所有的顶点相邻的边中，权值最小的边为 $(V_1,V_3)$ 和 $(V_3,V_4)$ 。说明Prim算法第二次选中的边可能是 $(V_1,V_3)$ 或 $(V_3,V_4)$ 。根据题意，排除这两条边，选C。