Prim's Algorithm

What is Prim's Algorithm?

Definition

Prim's algorithm calculates a possible minimum spanning tree of a given graph. This means that it takes a connected and weighted graph, and creates a subset where the graph is still connected, but with the lowest possible cumulative edge weight.

Steps

1. Select the start node. This is our subtree.
2. Find the lowest cost edge that connects a node in our subtree to a node not in our subtree.
3. Continue repeating step 2 until our subtree contains all the nodes in the original graph. The connected graph will be a minimum spanning tree.

Image of Prim's Algorithm

Pros

• Will always find a minimum spanning tree.
• Works well on graphs that have a large number of edges (relative to nodes).
• Can work with both adjacency lists and matrices (portable).

Webpage with Additional Information

W3Schools: Prim's Algorithm