Prim’s Algorithm

Prim’s algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959.

Prim’s Algorithm is a greedy algorithm that finds a Minimum Spanning Tree (MST) for a connected, weighted, undirected graph.

A Minimum Spanning Tree (MST):

• Includes all vertices,
• Has no cycles,
• Has the minimum total edge weight.

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.

How Prim’s Algorithm Works?

1. Select any starting vertex.
2. Mark it as visited.
3. From all edges that connect visited to unvisited nodes, choose the minimum weight edge.
4. Do not select a vertex that would produce a cycle (closed loop).
5. Add the edge and mark the vertex as visited.
6. Repeat until all vertices are included in the MST.
7. The number of edges in the MST is calculated as edges = (vertices - 1).

Example: Prim’s Algorithm

Consider a graph with vertices A, B, C, D, and E, and the following edge weights.

Step-by-Step Execution (Start from Vertex A):

Step 1: Start at A

Visited: {A}

Available Edges: A – B (2), A – C (3)

Choose: A – B (2)

MST: A – B (2)

Step 2: Visited: {A, B}

Available: B – C (1), A – C (3), B – D (4)

Choose: B – C (1)

MST: A – B (2), B – C (1)

Step 3: Visited: {A, B, C}

Available: B – D (4), C – D (5), C – E (6)

Choose: B – D (4)

MST: A – B (2), B – C (1), B – D (4)

Step 4: Visited: {A, B, C, D}

Available: C – E (6), D – E (7)

Choose: C – E (6)

MST: A – B (2), B – C (1), B – D (4), C – E (6)

Total Weight = 2 + 1 + 4 + 6 = 13

All vertices are now included.

Example 2: Prim’s Algorithm

A telecommunications company is contracted to connect six towns in Cork and South Tipperary with high speed fibre optic cabling.

Determine the lowest price to complete the project if the fibre optic cable is estimated to cost €10,000 per kilometre.

Details of the network framework is shown in Figure 1.

Instructions

Select any random town (vertex) as the starting point (e.g. Mallow) in Figure 2.

Select the shortest distance (Edge) from this point to the next unvisited town in Figure 3.

Continue by selecting the shortest distances to the next unvisited town without completing a cycle in Figure 4.

Continue by selecting the shortest distances to the next unvisited town without completing a cycle in Figure 5.

Continue to select an unvisited vertex, but the graph must remain acyclic in Figure 6.

In Figure 7 , Cork to Mallow cannot be selected as it would form a cycle as would Bandon to Midleton.

Bandon to Macroom is therefore the chosen option as it is the shortest remaining distance (30 Km).

In Figure 8, the only remaining option available is Fermoy to Cahir as any other route selected would form a cycle. This completes the graph.

Formula for the total number of edges is

Total Edges = Vertex - 1

Edges = (7 - 1) = 6

Having calculated the MST we can determine the shortest length of fibre optic cabling required & the lowest cost to connect all towns is €1,850,000.

Time and Space Complexity

Space Complexity: O(V + E)

Advantages of Prim’s Algorithm

• Efficient for dense graphs (especially with adjacency matrix).
• Can start from any vertex.
• Builds MST incrementally using visited-unvisited logic.

Disadvantages of Prim’s Algorithm

• Not suitable for disconnected graphs (must be connected).
• Slightly harder to implement than Kruskal’s due to heap logic.

Applications of Prim’s Algorithm

• Network Design (wiring, telephone, internet)
• Designing road or rail networks
• Clustering in Machine Learning
• Approximation for NP-hard problems

Prim’s vs Kruskal’s Algorithm