Trees · Minimum Spanning Tree

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Another algorithm for finding the minimum spanning tree is Prim's algorithm: we start with an arbitrary vertex, and in each iteration, we add a new vertex to the current tree using the lightest edge. Its correctness also follows from the cut property: as \(S\) we can take all vertices of the current tree.

For the curious 🤓

Both algorithms can be implemented in time \(O(|E|\log|V|)\). In the standard implementation of Kruskal's algorithm, a disjoint-set data structure is used, while in Prim's algorithm, a priority queue is used.