Using array instead of disjoint-set for Kruskals Algorithm for faster merge and find times

Question

so just learnt about Kruskals' Algorithm for Minimum Spanning Trees. So here's my understanding:

It initializes a disjoint-set data structure which contains all vertices V.

After sorting the edges by weight in |E|log|E| time or |E| time using counting sort (if the weights permit), Kruskals' algorithm iterates through the sorted edges and adds the edge (u,v) to the Minimum Spanning tree if the nodes u and v are not part of the same set in the disjoint set structure.Wikipedia says that the lookup and search times in this disjoint-set structure is a(V) where a is the inverse of the Ackermann function.

I feel like this lookup could be sped up but not 100% sure on complexity. Here's what I propose:

For each vertex in the graph, assign it a value from 0 to |V|-1, these numbers are now their indexes. Initialize an array of size |V| with all values set to 0.

When iterating through our edges (u,v) we can look up their indexes in O(1) time in the array, if either one of these array values is 0 then we set them both to 1 and add this edge to our minimum spanning tree.

It feels like doing it this way we can it O(V) time which better than O(a(V)) for looking up and merging sets in Kruskals' Algorithm at the cost of |V| space since we need to store an extra value for each vertex.

Does this seem right or am I just delusional with array access times?

Answer 1

Your algorithm fails for A--1--B--3--C--2--D (the letters are vertexes and numbers are weights).

Note, however, that you can implement a complete disjoint set data structure using just an array, and in fact it is often done. I use a representation like this:

• Each vertex has an index in the array (just like yours)
• Initialize all array elements to -1. An array value < 0 indicates the root of a set with the negation of the value giving its size or rank. All vertexes start off in their own set of size 1.
• If an array value is >=0, it indicates a set that is linked to a the parent set at that index. When you merge two sets, you set the value of the smaller one to the index of the larger, and adjust the size of the larger if necessary. It doesn't matter that you overwrite the size of the smaller set. It will never be a root so you'll never need the size again.