Minimum Spanning Tree – Prim’s Algorithm

In the previous lesson, we learned how topological sorting helps us order tasks while respecting dependencies.

Now we move into a different class of graph problems — network optimization.

This lesson introduces the idea of a Minimum Spanning Tree (MST) and explains Prim’s Algorithm, one of the most widely used approaches to build it.

What Is a Minimum Spanning Tree?

Given a connected, weighted, undirected graph, a Minimum Spanning Tree is a subset of edges that:

• Connects all vertices
• Contains no cycles
• Has the minimum possible total edge weight

In short:

Connect everything at the lowest possible cost.

Real-World Motivation

Minimum spanning trees appear naturally in many systems:

• Designing road networks
• Electrical grid layout
• Computer network cabling
• Telecommunication planning

The goal is always the same — connect all locations using the least total cost.

Why Greedy Algorithms Work Here

Prim’s algorithm is a greedy algorithm.

At each step, it chooses the cheapest edge that expands the existing tree without creating a cycle.

This local greedy choice leads to a global optimum.

Prim’s Algorithm – Core Idea

Prim’s algorithm starts with any one vertex and repeatedly:

• Selects the minimum-weight edge
• That connects the tree to a new vertex

The process continues until all vertices are included.

Graph Example

Consider the following weighted graph:

graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1},
    'C': {'A': 3, 'B': 1, 'D': 4},
    'D': {'B': 1, 'C': 4}
}

Prim’s Algorithm – Implementation

We will use a priority queue to always pick the lowest-cost edge.

import heapq

def prim(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_cost = 0

    while min_heap:
        cost, node = heapq.heappop(min_heap)

        if node in visited:
            continue

        visited.add(node)
        total_cost += cost

        for neighbor, weight in graph[node].items():
            if neighbor not in visited:
                heapq.heappush(min_heap, (weight, neighbor))

    return total_cost

print(prim(graph, 'A'))

This code guarantees the minimum total connection cost.

How the Algorithm Thinks

Prim’s algorithm grows the tree gradually.

At each step:

• Only edges touching the current tree are considered
• The cheapest valid edge is selected

This prevents cycles while minimizing cost.

Time Complexity

Using a priority queue, the time complexity is:

O(E log V)

This makes Prim’s algorithm efficient for large sparse graphs.

Prim vs Kruskal (Preview)

Prim’s algorithm grows from a single node outward.

Kruskal’s algorithm (next lesson) builds the MST by sorting all edges first.

Both solve the same problem using different strategies.

Mini Practice

Imagine connecting offices in a company using the cheapest fiber cables.

Why should cycles be avoided?

Because cycles add unnecessary cost.

Exercises

Quick Quiz

In the next lesson, we will study Kruskal’s Algorithm and compare it directly with Prim’s approach.