Creating worse case scenarios with kruskal's algorithm

Question

I have an implementation of Kruskal's algorithm in C++ (using disjoint data set structure). I'm trying to find possible methods of creating worse case scenario test cases for the total running time of the algorithm. I'm confused however on what can make the algorithm result in a worst case scenario when trying to create test cases and was wondering if anyone here might know of possible scenarios that would really make Kruskal's algorithm struggle.

As of now the main test I've considered that might theoretically test the bounds of Kruskal's algorithm would be test cases where all weights are the same. An example would be like the following:

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

What I end up running into is that regardless of what I do, if I try to slow down the algorithm I just end up with no minimum spanning tree and end up failing to actually test the bounds of the algorithm.

Answer 1

To stress Kruskal's algorithm, you need a graph with as many redundant edges as possible, and at least one necessary edge that will be considered last (since Kruskal's algorithm sorts the edges by weight). Here's an example.

The edges with weight 1 are necessary, and will be taken first. The edges with weight 2 are redundant and will cause Kruskal's algorithm to waste time before getting to the edge with weight 3.

Note that the running time of Kruskal's algorithm is determined primarily by the time to sort the edges by weight. Adding additional redundant edges of medium weight will increase the sort time as well as the search time.

Answer 2

Kruskal's algorithm consists of two phases - sorting the edges and than performing union find. If you implement the second phase using disjoint set forest and applying the path compression and union by rank heuristics, the sorting will be much slower than the second phase. Thus to create a worst case scenario for Kruskal you should simply generate a worst case scenario for the sorting algorithm you are using. If you use the built-in sorting, it has an optimization that will actually make it work way faster for already sorted array.