Prim’s Algorithm for Minimum Spanning Trees

Many problems involve connecting locations, computers, or services as cheaply as possible. A road network linking Sydney suburbs, cables connecting Melbourne data centres, or power lines serving regional Queensland can be represented as a weighted graph. The vertices represent locations, the edges represent possible connections, and each weight represents cost, distance, time, or another measurable quantity.

Prim’s algorithm finds a minimum spanning tree (MST) for a connected, undirected, weighted graph. The result connects every vertex with the smallest possible total edge weight and contains no cycles. This tutorial explains the greedy idea behind Prim’s method, gives pseudocode, analyses its complexity, and shows a practical Python implementation.

Understanding Minimum Spanning Trees

A spanning tree is a subgraph that includes every vertex in the original graph while remaining connected and acyclic. If a graph has (V) vertices, any spanning tree contains exactly (V - 1) edges. Removing any one of those edges disconnects the tree, while adding another edge creates a cycle.

A minimum spanning tree is the spanning tree with the lowest total weight. It does not necessarily provide the shortest route between every pair of vertices. That distinction matters: Dijkstra’s algorithm finds shortest paths from a starting point, whereas Prim’s algorithm minimises the cost of the entire connection structure.

For example, suppose a council wants to connect several suburbs with fibre optic cable. A minimum spanning tree identifies a set of cable links that reaches every suburb without unnecessary loops. If the edge weights represent installation cost, the tree minimises the total construction expense. If they represent physical distance, it minimises the total cable length.

Prim’s algorithm applies to connected, undirected graphs. If the input graph is disconnected, no single spanning tree can cover all vertices. In that situation, a modified run produces a minimum spanning forest: one minimum spanning tree for each connected component.

The Greedy Choice Behind Prim’s Algorithm

Prim’s method begins with any chosen vertex and gradually grows a tree. At each stage, it examines every edge that leaves the current tree and selects the cheapest one leading to a vertex not yet included. This is a greedy strategy because it commits to the locally cheapest safe edge.

The key safety rule is known as the cut property. Imagine dividing the vertices into two groups: those already in the tree and those outside it. The lightest edge crossing that division can belong to some minimum spanning tree. Adding it cannot force an unnecessarily expensive result, so the algorithm can safely expand through that edge.

A priority queue makes the repeated selection efficient. Each candidate edge is stored with its weight and destination. The smallest weight is removed first. If a vertex has already been included, an old queue entry is ignored; this lazy approach avoids needing a specialised decrease-key operation.

The algorithm continues until every vertex is part of the tree. The selected edges form the MST, and adding their weights gives its total cost. Equal-weight edges can lead to different valid trees, but all such trees have the same minimum total weight.

Pseudocode and Complexity

A typical adjacency-list version keeps three pieces of information: a set of visited vertices, a min-priority queue of candidate edges, and a collection of selected MST edges. The starting vertex is marked as available by inserting a zero-cost entry into the queue.

The core pseudocode is:

choose a start vertex
push (0, start, no_parent) into a min-priority queue
total_cost = 0
mst_edges = []

while the priority queue is not empty:
    weight, vertex, parent = remove the smallest item

    if vertex is already visited:
        continue

    mark vertex as visited
    total_cost += weight

    if parent exists:
        add (parent, vertex, weight) to mst_edges

    for each (neighbour, edge_weight) of vertex:
        if neighbour is not visited:
            push (edge_weight, neighbour, vertex)

With an adjacency list and a binary heap, the time complexity is (O(E \log E)), where (E) is the number of edges. It is also commonly written as (O(E \log V)), because the heap contains a manageable number of entries relative to the graph size. The space complexity is (O(V + E)), accounting for the graph, heap, visited set, and result.

For a dense graph stored as an adjacency matrix, a straightforward implementation that scans all possible neighbours can run in (O(V^2)) time. That version may be suitable for small dense inputs. For sparse networks, the heap-based approach is generally the better choice. A detailed Prim algorithm walkthrough can be useful when comparing these implementation styles and tracing the greedy decisions.

Python Implementation With A Heap

Python’s heapq module provides the min-heap operations needed by Prim’s algorithm. The graph below uses a dictionary in which each vertex maps to a list of (neighbour, weight) pairs. Because the graph is undirected, every connection must be stored in both directions.

import heapq

def prim_mst(graph, start):
    visited = set()
    heap = [(0, start, None)]
    mst_edges = []
    total_cost = 0

    while heap:
        weight, vertex, parent = heapq.heappop(heap)

        if vertex in visited:
            continue

        visited.add(vertex)
        total_cost += weight

        if parent is not None:
            mst_edges.append((parent, vertex, weight))

        for neighbour, edge_weight in graph[vertex]:
            if neighbour not in visited:
                heapq.heappush(
                    heap,
                    (edge_weight, neighbour, vertex)
                )

    if len(visited) != len(graph):
        raise ValueError("The graph is disconnected")

    return mst_edges, total_cost

A sample graph can represent connections between locations:

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("C", 1), ("D", 5)],
    "C": [("A", 2), ("B", 1), ("D", 8)],
    "D": [("B", 5), ("C", 8)]
}

edges, cost = prim_mst(graph, "A")
print(edges)
print(cost)

The function returns three selected edges and a total cost of 8. Heap entries can become stale after a cheaper route to a vertex is discovered. That is expected: the visited check discards the stale entry when it reaches the top of the heap. This technique keeps the code simple and still provides the required performance.

If edge weights come from numerical data, NumPy can help prepare or transform those values before graph construction. For example, a project processing arrays of distances or costs may benefit from NumPy broadcasting, though the heap itself still operates on individual Python tuples.

Tracing An Example Graph

Starting from vertex A in the sample graph, the algorithm first considers edges A–B with weight 4 and A–C with weight 2. It chooses A–C because 2 is smaller. The tree now contains A and C, and the frontier includes A–B with weight 4, C–B with weight 1, and C–D with weight 8.

The next choice is C–B with weight 1. From the three included vertices, the available edges to D include B–D with weight 5 and C–D with weight 8. The algorithm selects B–D, producing the tree edges A–C, C–B, and B–D. Their combined weight is (2 + 1 + 5 = 8).

Notice that the edge C–D with weight 8 is never selected. It would create a cycle if B–D had already connected D to the existing tree. Prim’s algorithm does not need to inspect every possible final tree; it maintains a growing connected structure and rejects edges that lead to visited vertices.

Several implementation details deserve attention. Negative edge weights are allowed because the algorithm compares edge costs rather than accumulating path estimates. Parallel edges are also valid; the lower-cost connection will normally be selected. Self-loops should be ignored because they cannot help connect a new vertex. An empty graph requires a clearly defined policy, such as returning an empty tree or raising an exception.

Practical Guidance For Reliable Implementations

Prim’s algorithm is a strong option when the graph is undirected and the goal is to connect all locations with minimum total infrastructure cost. It is especially convenient when starting from one vertex and progressively exploring nearby connections. Kruskal’s algorithm is another MST method and may be preferable when edges are already available as a sorted list or when a disjoint-set data structure fits the application better.

Australian examples make the modelling choices concrete. A network designer might use an MST as a first approximation for linking facilities around Brisbane, while a mining operation in Western Australia could model remote sites and access links with very different edge costs. A graph based on NBN-style infrastructure could use installation expense rather than geographic distance, since trenches, difficult terrain, and existing conduits change the practical price of a connection.

Use the following checks when building or reviewing a solution:

• Represent every undirected edge in both adjacency lists.
• Confirm that the graph is connected before reporting a single MST.
• Store (weight, vertex, parent) in a min-heap so selected edges can be reconstructed.
• Ignore heap entries whose vertices have already been visited.
• Count the returned edges and verify that a connected graph with (V) vertices has (V - 1) of them.
• Use a numeric type large enough for the total cost when processing large infrastructure datasets.

In Australian software interviews and university assignments, it is common to be asked for both an implementation and a complexity explanation. State why the heap is used, explain the cut property in plain language, and distinguish an MST from shortest-path output. Testing with a small graph, a graph containing equal weights, a single vertex, and a disconnected input will expose most practical errors.