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.