Create graph to force Kruskal's algorithm to w

问题:

I wanna make a grpah with many nodes to force kruskal algorithm in worst case scenario. What kind of graph should it be ? I im stuck .

回答1:

Supposing you are implementing kruskal algorithm with dijoint sets, and sorting the edges with a stable and "fast" algorithm you will have O(E log E) worst case. You can also have E = O(V^2), so worst case will also be O(E log V). We can conclude that running time is dominated by heap operations so typically the algorithm terminates before considering all edges, so faster in practice. Considering all of this, in order to reproduce the worst case scenario all you have to do is maximize your graph, considering that each vertex will have edges connecting to all other vertexes.