Prim's Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 9: Line 9:
=Non-Optimized Implementation=
=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.
The Prim algorithm randomly selects a node. It then enters a loop where at each iteration adds a new edge and spans one new vertex, adjacent to the ones already spanning. The new vertex added to the "explored territory" is selected so it can be reached via the cheapest edge. This is what makes Prim's algorithm a [[Algorithms#Greedy_Algorithms|greedy algorithm]].

Revision as of 22:07, 20 October 2021

External

Internal

Overview

Even if the algorithm was named after Prim, it was discovered earlier by Jarník. The algorithm is similar to Dijkstra's shortest-path algorithm.

Non-Optimized Implementation

The Prim algorithm randomly selects a node. It then enters a loop where at each iteration adds a new edge and spans one new vertex, adjacent to the ones already spanning. The new vertex added to the "explored territory" is selected so it can be reached via the cheapest edge. This is what makes Prim's algorithm a greedy algorithm.