Prim’s Algorithm for Minimum Spanning Trees

Prim’s algorithm is a greedy graph algorithm for finding a minimum spanning tree (MST) in a connected, weighted, undirected graph. It starts with one vertex and repeatedly adds the cheapest edge that connects the growing tree to a vertex outside it. The result connects every vertex with the smallest possible total edge weight and contains no cycles.

This makes Prim’s algorithm useful for designing networks, clustering infrastructure, and solving graph problems efficiently. A road, fibre, power, or computer network can be represented as a graph, where locations are vertices and possible connections are weighted edges. The algorithm then selects a cost-effective set of links that reaches every location.

Minimum Spanning Tree Basics

A spanning tree is a subgraph that includes every vertex in the original graph and has exactly enough edges to remain connected without creating a cycle. If a graph has (V) vertices, any spanning tree contains (V-1) edges. A minimum spanning tree is the spanning tree with the lowest possible sum of edge weights.

The weights can represent distance, construction cost, latency, cable length, or risk. For example, a telecommunications company connecting sites in Sydney could use distances or estimated installation costs as edge weights. A council planning links between facilities in Melbourne might use projected construction costs instead.

An MST is different from a shortest-path tree. A shortest-path algorithm minimises the route from one chosen source to other vertices. An MST minimises the total cost of the entire network, so the route between two particular vertices is not necessarily the shortest available route.

The Greedy Idea Behind Prim’s Algorithm

Prim’s algorithm follows a local decision rule: among all edges leaving the current tree, choose the minimum-weight edge that reaches an unvisited vertex. This is safe because the cheapest edge crossing from the selected set of vertices to the unselected set can belong to an MST, a property known as the cut principle.

The algorithm does not reconsider the whole graph after every choice. Instead, it maintains a boundary between vertices already included in the tree and vertices still outside it. Each chosen edge expands that boundary by one vertex. This greedy strategy produces a globally optimal result for undirected graphs with suitable edge weights.

The approach is closely related to Kruskal’s algorithm, although the two algorithms grow their solutions differently. A useful comparison of their mechanics and complexity appears in this Kruskal algorithm guide.

How The Algorithm Builds A Tree

Prim’s algorithm can begin at any vertex. The starting choice may change the order in which edges are selected, but it will not change the total weight of the final MST when the graph is connected and the relevant edge weights are fixed. If several edges have the same weight, multiple valid MSTs may exist.

A common implementation stores the cheapest known connection for every unvisited vertex. At each step, it extracts the vertex with the smallest key value, adds that vertex to the tree, and examines its neighbours. If an edge offers a cheaper connection than the current recorded value, the key and parent of that neighbour are updated.

A simple version of the process is:

choose a starting vertex
set its key to 0 and every other key to infinity
repeat until every vertex is included:
    select the unvisited vertex with the smallest key
    mark it as included
    add its parent edge to the MST, unless it is the start
    for each adjacent edge:
        if the neighbour is unvisited and the edge is cheaper:
            update the neighbour's key and parent

The parent array records how each vertex entered the tree. The key array records the lowest edge currently known to connect that vertex to the selected set. Together, these arrays are enough to reconstruct the MST.

Data Structures And Complexity

An adjacency list is usually the best graph representation for Prim’s algorithm when the graph is sparse. Each vertex stores its neighbouring vertices and edge weights. A priority queue, commonly implemented as a binary heap, quickly identifies the unvisited vertex with the smallest connection cost.

The complexity depends on the data structures used. With an adjacency matrix and a linear search for the next vertex, the running time is (O(V^2)). With an adjacency list and a binary heap, it is (O(E \log V)), where (V) is the number of vertices and (E) is the number of edges. The space requirement is (O(V+E)) for an adjacency-list implementation.

Implementation approach	Graph representation	Time complexity	Typical use
Linear search	Adjacency matrix	(O(V^2))	Dense graphs and simple teaching examples
Binary heap	Adjacency list	(O(E \log V))	General sparse graphs
Fibonacci heap	Adjacency list	(O(E + V\log V))	Theoretical or specialised performance work
Array-based scan	Adjacency list	Up to (O(V^2))	Small graphs with simple code requirements

For a dense graph, the matrix-based approach may be practical because many possible edges already exist. For a large sparse network, such as links between regional facilities, the heap-based approach usually avoids scanning a large number of absent edges.

Python Implementation With A Heap

Python’s heapq module provides a min-heap suitable for Prim’s algorithm. The heap stores pairs containing an edge weight and a destination vertex. When a better connection is found, a new pair is pushed onto the heap. Python’s heap does not support directly decreasing an existing key, so the implementation skips stale entries when they are removed.

import heapq

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

    while heap and len(visited) < len(graph):
        weight, vertex, parent = heapq.heappop(heap)

        if vertex in visited:
            continue

        visited.add(vertex)

        if parent is not None:
            mst_edges.append((parent, vertex, weight))
            total_weight += 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_weight

The graph can be represented as a dictionary whose values are adjacency lists. For an undirected graph, every edge must be added in both directions.

graph = {
    0: [(1, 4), (2, 2)],
    1: [(0, 4), (2, 1), (3, 5)],
    2: [(0, 2), (1, 1), (3, 8)],
    3: [(1, 5), (2, 8)]
}

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

The check for a disconnected graph matters. Prim’s algorithm produces a complete MST only when every vertex is reachable from the starting vertex. If the graph has several disconnected components, the algorithm can instead be adapted to run from each unvisited component and return a minimum spanning forest.

Reading The Result In A Practical Setting

Suppose four sites are connected with these candidate links: site 0 to site 1 with weight 4, site 0 to site 2 with weight 2, site 1 to site 2 with weight 1, site 1 to site 3 with weight 5, and site 2 to site 3 with weight 8. Starting at site 0, Prim’s algorithm selects the edge of weight 2 to site 2, then the edge of weight 1 to site 1, and finally the edge of weight 5 to site 3.

The resulting total is 8, using three edges for four vertices. The edge of weight 8 is rejected because site 3 can already be reached more cheaply through site 1. The edge of weight 4 is also rejected because sites 0 and 1 are connected through site 2 at a lower total cost.

Useful checks make an implementation easier to test:

• The result should contain exactly (V-1) edges for a connected graph.
• The selected edges should connect every vertex.
• The selected edges should contain no cycle.
• The sum of selected weights should match the reported total.
• A disconnected input should be detected rather than silently accepted.

This model can describe a small network of university buildings in Brisbane, links between remote mining sites in Western Australia, or a simplified plan for connecting substations across an Australian energy project. Real engineering decisions would include resilience, capacity, terrain, and regulatory requirements as well as cost.

Choosing Prim’s Algorithm Carefully

Prim’s algorithm is especially convenient when the graph is stored as adjacency lists and the solution should grow from a chosen starting point. It works well for dense graphs and can be adapted to large sparse graphs with a priority queue. Since it examines connections from the current tree, it also fits situations where neighbouring relationships are already available.

Kruskal’s algorithm may be a better choice when edges are already available as a sorted list. Kruskal processes edges globally and uses a disjoint-set data structure to avoid cycles, while Prim maintains one expanding component. Both algorithms find an MST, but their implementation details and performance can differ according to the graph’s shape.

Common mistakes include treating a directed graph as if it were undirected, forgetting to add both directions for an undirected edge, and confusing edge weights with vertex values. Another frequent error is using Prim’s algorithm to solve a shortest-path problem, where Dijkstra’s algorithm is usually the appropriate tool.

For clear explanations of graph algorithms, code, and complexity, the open hello ML community provides educational material aimed at learners and programmers building practical foundations.

Testing And Edge Cases

A reliable implementation should be tested with graphs that expose different behaviours. Include a graph with one vertex, a graph containing equal-weight edges, a dense graph, and a disconnected graph. Testing negative edge weights can also clarify an important point: Prim’s algorithm can still work with negative weights, provided the graph is undirected and the comparison logic is correct.

The following cases are particularly useful:

• A single vertex should return an empty edge list and total weight zero.
• A triangle should select the two cheapest edges without forming a cycle.
• Equal-weight alternatives may produce different but equally valid MSTs.
• A disconnected graph should return an error or a minimum spanning forest.
• Repeated edges should be handled according to the graph model and input rules.

In a production network, the mathematical MST may still be too fragile if every selected link is essential. Australian infrastructure planners might add backup routes around flood-prone areas, bushfire corridors, or remote locations where repairs are difficult. Prim’s algorithm supplies the minimum-cost baseline; operational constraints determine whether that baseline is suitable for deployment.