Prim’s works by starting at any vertex, and finding the minimum edge weight between a tree and a non-tree vertex. It will then add that minimum edge and vertex to the minimum spanning tree.
Kruskal’s first sorts all the edges of a graph by weight, and inserts them into a priority queue. It then loops through the priority queue, getting the edge with the lowest weight, and checks if it will create a cycle in the minimum spanning tree. If it would not, it will add that edge to the minimum spanning tree, and merge the two vertices.
- Kruskal’s offers a little bit of control over the minimum spanning tree as it always begins at the same spot, however, because Prim’s starts at an arbitrary vertex, it is a bit harder to control.
- Both algorithms can be implemented using a priority queue, however, Kruskal’s also makes use of disjoint sets and a Union-Find class.
- The default time complexity of Prim’s algorithm is n iterations each looping through all possible edges m, making the time complexity O(nm), however, this can be improved to O(n²) when using a priority queue. On the other hand, the time complexity of Kruskal’s is simply O(E log(V)), E being edges, and V being vertices.
- Prim’s algorithm performs best when the given graph is very dense, whereas Kruskal’s performs best when the given graph is sparse.
Kruskal's vs Prim's Algorithm | Baeldung on Computer Science
In graph theory, there are two main algorithms for calculating the minimum spanning tree (MST): Kruskal's algorithm…