Hello, and welcome to my demonstration of Kruskal's algorithm! Head here to try out my project.
It is important to note that there are other methods of solving MST's. Boruvka's algorithm is very similar to Kruskal’s. First, it makes a list of n trees, each with a single point. Then, it finds the shortest edges that connects these trees until only one tree exists. Boruvka's algorithm thus has a complexity of O(e log n). Boruvka's is more efficient than Kruskal's since Kruskal requires the points to first be sorted. Another algorithm is Prim's algorithm, which first takes a single vertex and then connects to other points via the shortest edge until every point is connected. Prim's algorithm seems at first more complex since edges must be analyzed at every step, whereas Kruskal’s contains a pre-sorted list of edges and Boruvka's implements parallelization to evaluate every point per step. However, Prim's can become the most efficient of the three by using more complex data structures. By using a binary or Fibonacci heap, Prim's can go from O(en) to O(e + n log n) or O(e + log n), respectively. So how does Kruskal’s compare? The linear implementation of Kruskal's in this program is the most complex of them all: O(m log n) to sort and O(en) to execute. So why did I use Kruskal's in this program? Kruskal is most useful for competitive programming in which the problem's time constraint allows for a certain amount of greed because it is the fastest algorithm to implement. With knowledge of MST’s, Kruskal’s can be written in under five minutes. And as this program should show, a linear implementation of Kruskal is plenty for most greedy problems. As a bonus, if Kruskal's does not meet the time constraint, switching to Boruvka's is quick and easy.
This was just a quick little project I did to learn something new. Going forward I'd like to try other demonstrations of different algorithms, since I feel like I’ve learned quite a bit on this project. I used this project to help me analyze a problem I encountered that I didn’t understand, and it has definitely helped me “upsolve” the problem.