c++ - 使用 kruskal 算法创建更坏的情况

Question

我在 C++ 中实现了 Kruskal 算法（使用不相交的数据集结构）。我试图找到为算法的总运行时间创建更坏情况测试用例的可能方法。然而，当我尝试创建测试用例时，我对什么会使算法导致最坏的情况感到困惑，并且想知道这里是否有人可能知道真正让 Kruskal 的算法陷入困境的可能场景。

到目前为止，我认为理论上可能测试 Kruskal 算法界限的主要测试将是所有权重都相同的测试用例。一个例子如下：

4 4 
(4, 4) 4 //(4,4) vertex and weight = 4
(4, 4) 4 
(4, 4) 4 
(4, 4) 4 

我最终遇到的是，无论我做什么，如果我试图减慢算法的速度，我最终会没有最小生成树，最终无法实际测试算法的边界。

Answer 1

为了强调 Kruskal 的算法，您需要一个具有尽可能多的冗余边的图，并且至少有一个必要的边将被最后考虑（因为 Kruskal 的算法按权重对边进行排序）。这是一个例子。

权重为 1 的边是必需的，将首先被取走。权重为 2 的边是多余的，会导致 Kruskal 算法在到达权重为 3 的边之前浪费时间。

请注意，Kruskal 算法的运行时间主要取决于按权重对边进行排序的时间。添加额外的中等权重的冗余边将增加排序时间和搜索时间。

Answer 2

Kruskal 的算法包括两个阶段 - 对边进行排序和执行联合查找。如果您使用不相交集森林来实现第二阶段，并通过等级启发式应用路径压缩和联合，则排序将比第二阶段慢得多。因此，要为 Kruskal 创建最坏的情况，您应该简单地为正在使用的排序算法生成最坏的情况。如果您使用内置排序，它有一个优化，实际上可以使它对已经排序的数组更快地工作。