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 算法的运行时间主要取决于按权重对边进行排序的时间。添加额外的中等权重冗余边会增加排序时间和搜索时间。