Prim's Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

For graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.

1.  Start at any node in the graph.

Mark the starting node as reached.

Mark all the other nodes in the graph as unreached.

#Minimum cost Spanning Tree (MST) consists of the starting node.

2. Find an edge e with minimum cost in the graph that connects a reached node x to an unreached node y.

3. Add the edge e found in the previous step to the MST.

Mark the unreached node y as reached.

4. Repeat the steps 2 and 3 until all nodes in the graph have become reached.

Pseudo code

ReachSet = {0};                    // You can use any node...

UnReachSet = {1, 2, ..., N-1};

SpanningTree = {};

while ( UnReachSet ≠ empty ) {

              Find edge e = (x, y) such that:

                    x ∈ ReachSet

                    y ∈ UnReachSet

                    e has smallest cost

              SpanningTree = SpanningTree ∪ {e};

              ReachSet   = ReachSet ∪ {y};

              UnReachSet = UnReachSet - {y};

}

Do you know it?

Developed by: Czech mathematician Vojtěch Jarník in 1930.

Rediscovered and republished by: computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959.