我正在尝试完成一些真/假问题。当我用 true 回答其中许多时,我开始担心... 请假设所有图表都是无向的并且没有不同的权重。负重应该没问题。
Qa) 如果 G 有一个具有唯一最重边 e 的循环,则 e 不能是任何 MST 的一部分。
我的回答是真的。例如,我们有一个包含节点 A、B、C、D、E 的图。
AB = 1
BC = 2
BD = 3
CD = 100
DE = 4
如您所见,BCD 是一个循环。我的论点是,既然它是一个循环,我们总是可以通过采取其他路线来避免独特的最重边缘 CD。因此这是真的。我的论点是否合理(足够)?
Qb) Dijkstra 算法计算的最短路径树必然是 MST。
我的回答是对的,但我的直觉告诉我出了点问题。嗯... Disjkstra 和 Prim 都是贪心算法。他们每次都选择最轻的加权边缘。是否存在最短路径树不是最小生成树的情况?我实际上很难理解这两个家伙之间的区别。
Qc) Prim 的算法适用于负加权边缘。
我的回答是真的。因为这就是 wiki 所说的...... :p 该算法是关于在所有边中找到成本最低的边。所以负加权边缘应该没关系,是吗?但是负加权循环呢?
Qd) 如果 G 有一个具有唯一最轻边 e 的循环,则 e 必须是每个 MST 的一部分。
我的回答是真的。我们必须访问 MST 中的所有节点。例如,在长度为 3 的循环中,我们总是可以用 2 步遍历该循环中的所有节点。如果有独特的最轻边缘,我们肯定会在 MST 中选择它。
我的主张合理吗?也许他们还不够?那么有什么建议吗?