带两种权重的MST-Kruskal算法

Question

TL，DR：当增长一个MST时，在有许多轻量级边缘可供选择的情况下，如何选择一个特定的MST加入MST？

我有一个通用的问题，我一直试图解决整个一天，但阅读我的算法书&搜索网络并没有帮助我。我无法分享我的代码，因为这是一个大学项目，基本上是我错过的唯一场景。

想象下面的问题。

我有一个N边图，我想找到它的MST（典型问题）。然而，除了具有将顶点u连接到顶点v的代价的边缘之外，这些相同的顶点可以具有特殊的标记，使得它们可以连接到具有相同特殊标记的所有其他边缘。

我回答了这个问题，通过创建一个特殊的顶点，与该标志连接到的所有顶点，与相应的成本。

一切工作正常。当MST有许多可能的解决方案时会出现问题。我应该输出一个使用最少量的特殊标志连接。

我知道读者可能很难在看不到我的代码的情况下提出建议。但不幸的是，我真的无法分享。

我能说的就是我定义的边缘，无论它是特殊或不作为结构{U，V，成本}

有一件事我tryed，被新月顺序排序的边缘矢量按照标准kruskal算法的要求，但每当权重相同时，将“特殊边缘”的边缘向前推入矢量。

所以我会有这样的东西 [成本1正常，成本1正常，成本1特殊，成本2，成本3，成本3特殊，...]。

任何意识？

感谢您的意见。

Answer 1

我认为你正在解释的内容似乎是正确的，但这是另一种看问题的方式。

在构建MST时，您只需比较与边缘相关的成本 - 您的代码无需做任何非常复杂的成本。

所以成本不一定是普通数字。他们可以有两个组成部分，一个用于通常的比较，另一个用作第一个组分比较相等时的平局。另一种看待这种情况的方式是说，所有的成本看起来有点像123.000000000000000000000456，其中在成本的第一部分和成本的第二部分之间有如此多的零，第二部分成本在除非第一部分是平等的，并且从第二部分直到第一部分从来​​没有任何形式的比较。

因此，在您的问题中，成本的第一部分将是边的普通权重，如果是特殊边，则第二部分成本为1，否则为0。在这种情况下，最低成本将是最低的普通成本，其中特殊边缘的数量用作决胜手。