TL,DR:在增长 MST 时，如果有很多轻量级边缘可供选择，我该如何选择特定的边缘添加到 MST 中？
我有一个一般性问题，我一整天都在尝试解决这个问题，但阅读我的算法书和搜索网络并没有帮助我解决问题。我不能分享我的代码，因为它是一个大学项目，它基本上是我错过的唯一场景。
想象一下下面的问题。
我有一个有 N 条边的图，我想找出它的 MST(典型问题)。然而，除了具有将顶点 u 连接到顶点 v 的成本的边之外，这些相同的顶点可能有一个特殊的标志，允许它们连接到具有相同特殊标志的所有其他边。
我通过创建一个特殊的顶点来解决这个问题，所有带有该标志的顶点都连接到该顶点，并具有各自的成本。
一切正常。当 MST 有许多可能的解决方案时，问题就出现了。我应该输出一个使用最少特殊标志连接的。
我知道读者可能很难在没有看到我的代码的情况下提出建议。但不幸的是，我真的不能分享。
我能说的是我正在定义一个 Edge，不管它是否特殊作为结构 {u, v, cost}
我尝试过的一件事是按照标准 kruskal 算法的要求按权重的新月顺序对边缘向量进行排序，但是只要权重相同，就会将“特殊边缘”的边缘向前推到向量中。
p>所以我会有这样的东西 [普通成本 1，普通成本 1，特殊成本 1，成本 2，成本 3，特殊成本 3，...]。
有什么想法吗？
感谢您的输入。
最佳答案
我认为您所解释的似乎是正确的，但这是看待问题的另一种方式。
构建 MST 时，您只需比较与边相关的成本 - 您的代码不必对成本做任何非常复杂的事情。
所以成本不必是普通数字。它们可以有两个组成部分，一个用于通常的比较，另一个在第一个组成部分比较相等时用作平局。另一种看待这个问题的方式是说所有成本看起来有点像 123.000000000000000000000456，其中成本的第一部分和成本的第二部分之间有太多的零，以至于成本的第二部分在比较，除非第一部分相等，并且从第二部分到第一部分从来没有任何形式的进位。
因此在您的问题中，成本的第一部分将是边的普通权重，如果是特殊边，成本的第二部分将为 1，否则为 0。在这种情况下，最低成本将是最低普通成本，特殊边的数量用作决胜局。
关于algorithm - 两种权值的MST-Kruskal算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43566761/