# Is this dense version of Kruskal's algorithm well-known?

About a year ago, a friend and I thought of a way to implement Kruskal's algorithm for dense graphs in better than the usual $O(m \log m)$ bound (without assuming pre-sorted edges). Specifically, we achieve $\Theta(n^2)$ in all cases, similar to Prim's when implemented using adjacency matrices.

I've posted a bit about the algorithm in my blog, including C++ code and benchmarks, but here's the general idea:

• Maintain one representative node for each connected component. Initially, all nodes represent themselves.

• Maintain a vector dist[i] such that, for every component i, has the lightest component-crossing edge incident to i.

• When finding the lightest edge that crosses partitions, simply find i that minimizes the weight of dist[i], in linear time.

• When joining two components $c_i$ and $c_j$, modify the adjacency matrix $A$, such that now $A_{i, k} = \min \{A_{i, k}, A_{j, k}\}$ for all components $k$, and mark $i$ as no longer representative of its connected component (only $j$ will now remain).

The contracting of the lightest edge and the finding of said edge can thus both be done in linear time. We do this $n - 1$ times to find the MST. A little bookkeeping is needed to actually find which edge we want to add to the MST, but does not increase the complexity. Thus the runtime is $\Theta(n^2)$. The implementation is just a couple of for loops.

Is this version of Kruskal well-known in the literature?

I'm not sure about this specific method for achieving $O(n^2)$ time, but two different methods for performing Kruskal in $O(n^2)$ time are given in my paper "Fast hierarchical clustering and other applications of dynamic closest pairs" (SODA 1998, arXiv:cs.DS/9912014, and J. Experimental Algorithms 2000):
As I wrote in 2011 in the Wikipedia article on the nearest-neighbor chain algorithm, that algorithm can also be used to perform Kruskal in $O(n^2)$ time. However (unlike some other applications of the nearest-neighbor chain algorithm) you don't get a space savings, so (like the quadtree method and your method) the space is still $O(n^2)$. In contrast Prim+sorting can use only $O(n)$ space beyond that needed to store the input.