如何寻找赋权图的每个最小生成树中必须存在的边

Question

给定一个无向加权图，边的实际权重是未知的；相反，每条边都被分类为轻、中或重。

所有轻边的权重都小于任何中边或重边。

所有中边的权重都比任何重边小。

通常，对于同一权重类中的两条边之间的关系一无所知。那么，如何识别这个图的每个MST中必须存在的所有边？以下是我的想法: 1.确定强连通分量的数量。2. MST中必须存在由铰接点组成的边。3.每个连接组件中最亮的边必须存在于MST中。

我不确定我的想法是否正确？如果是正确的，如何用java实现代码？非常感谢。

Answer 1

Jason，我不会深入描述如何在Java中实现代码，但让我们看看算法背后的思考过程。

由于您的顶点分为三个权重类别，我们可以使用比较权重重新标记它们，如下所示: Light为1；Medium为2；Heavy为3。这样，您的条件保持不变。

接下来，我们可以像往常一样使用Kruskal的最小生成树算法(MST)在无向加权图上创建最小生成树。这个算法是贪婪的，所以它会从轻到重排序边，选择下一个最小的边，只要它不创建一个循环，然后重复步骤2，直到所有的顶点都包含在MST中。(请参阅下面的链接以供参考) https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

当涉及到验证算法是否正确时，有两种潜在的情况。

1)。您可以显示MST中的边的实际权重以及排除的边的权重。检查排除的边，如果将排除的边添加到MST时，该边不是周期中最重的边，则将其与最重的边交换。继续执行此操作，直到探索完所有最初排除的边，并且MST保持其包含每个顶点的属性。2)。您不能显示图形中任何顶点的实际权重。在这种情况下，甚至无法验证您的算法是否创建了最小生成树，因此您的算法将无法进行自我检查。在任何情况下，使用具有比较权重的Kruskal算法都会创建一个非常接近最小的生成树，即使不知道实际权重。