代码之家 › 专栏 › 技术社区 › Abhijit Sarkar

对于MST,以下哪些选项是正确的?

minimum-spanning-tree graph-theory algorithm

Abhijit Sarkar · 技术社区 · 7 年前

考虑具有不同边成本的连通无向图。哪个以下哪项是真的?[勾选所有适用项。]

假设边不是穿过切割(,)的最便宜边。则不属于任何最小生成树。

最小生成树是唯一的。

据我所知,这四种选择都是正确的。选项1、2和4来自切割属性;选项3是正确的,因为边权重不同。然而,结果证明,包括选项1是错误的。为什么?

2 回复 | 直到 7 年前

Yola 7 年前

不

对

对

对于#1:

 A1 --- B1
        |
 A2 --- B2

假设 w(A1,B1) > w(A2,B2) ,但您仍然需要将这两个属性都包含到MST中。

Semih BoÄaz 7 年前

首先让我们看一下mst定义。mst是一个具有不同边代价的连通无向图的子集,它将所有顶点连接在一起,没有任何循环,并且具有最小可能的总边权重。

2.如果有一个循环C,那么我们不能谈论mst,它将是一个闭合路径。这就是循环的定义。

4.可能不是因为它会导致一个类似循环或电路的循环,所以我们不使用该边遍历a到B

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前