I am working on a problem in which I must find a graph with edge weights on n vertices, for which Kruskal's algorithm achieves worst-case running time. I am using a UNION-FIND data structure, but with no optimisations (path compression or weight/height union rules).
The version of Kruskal's which I am using is as follows:
Kruskal(G)
for each vertex π£ β π do MAKEβSET(π£)
sort all edges in non-decreasing order
for edge π’, π£ β πΈ (in the non-decreasing order) do
if FIND π’ β FIND(π£) then
colour (π’, π£) blue
UNION(π’, π£)
od
return the tree formed by blue edges
Also, MAKE-SET(x), UNION(x, y) and FIND(x) are defined as follows:
MAKE-SET(π)
Create a new tree rooted at π₯
PARENT(π₯)=x
UNION(π, π)
PARENT FIND(π₯) β πΉπΌππ·(π¦)
FIND(π)
π¦ β π₯
while π¦ β PARENT(π¦) do
π¦ β PARENT(π¦)
return y
After having looked at this post, my idea was to construct a graph on n vertices, such that there are as many redundant edges as possible and at least one necessary edge which is checked last (this edge must have the greatest weight).
I've looked at the specific cases n = 4 and n = 5 and have tried to construct such graphs in these cases. However, I am struggling to generalise to arbitrary n.
I would appreciate any hints for progressing with this problem. Thank you.