Prim's Algorithm

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/tQ6gK/prims-mst-algorithm
• https://en.wikipedia.org/wiki/Prim's_algorithm

Internal

• The Minimum Spanning Tree Problem

Overview

Even if the algorithm was named after Prim, it was discovered earlier by Jarník.

Non-Optimized Implementation

The Prim algorithm randomly selects a node and then, in a loop where at each iteration a new node is added to the "explored territory", it selects the node that can be reached via the cheapest edge.