Prim Algorithm: What It Is and How It Works

The Prim algorithm is a method to find a minimum spanning tree in a weighted graph by starting from one node and growing the tree by adding the smallest edge connecting the tree to a new node. It ensures all nodes are connected with the least total edge weight.

How It Works

Imagine you want to connect several houses with roads so that every house is reachable from any other, but you want to spend the least money building roads. The Prim algorithm helps by starting from one house and always choosing the cheapest road that connects a new house to the group already connected.

It works step-by-step: first, pick any starting node. Then, look at all edges that connect this node to others not yet connected. Choose the edge with the smallest weight and add that new node to your tree. Repeat this process, always picking the smallest edge that connects the tree to a new node, until all nodes are included.

This way, the algorithm builds a tree that connects all nodes with the minimum total edge cost, called the minimum spanning tree.

Example

This example shows Prim algorithm finding a minimum spanning tree for a small graph represented by an adjacency matrix.

python

def prim_algorithm(graph):
    n = len(graph)
    selected = [False] * n
    selected[0] = True
    edges = []

    for _ in range(n - 1):
        minimum = float('inf')
        x = 0
        y = 0
        for i in range(n):
            if selected[i]:
                for j in range(n):
                    if not selected[j] and graph[i][j] != 0:
                        if graph[i][j] < minimum:
                            minimum = graph[i][j]
                            x, y = i, j
        edges.append((x, y, graph[x][y]))
        selected[y] = True
    return edges

# Graph represented as adjacency matrix
# 0 means no edge
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

mst = prim_algorithm(graph)
for edge in mst:
    print(f"Edge from {edge[0]} to {edge[1]} with weight {edge[2]}")

Output

Edge from 0 to 1 with weight 2
Edge from 1 to 2 with weight 3
Edge from 1 to 4 with weight 5
Edge from 0 to 3 with weight 6

When to Use

Use Prim algorithm when you need to connect all points in a network with the least total cost, such as designing road systems, computer networks, or electrical grids. It works best on dense graphs where many edges exist because it efficiently grows the minimum spanning tree by always choosing the smallest connecting edge.

For example, a city planner might use Prim algorithm to decide which roads to build to connect neighborhoods with minimal construction cost. Similarly, network engineers use it to design cost-effective wiring or fiber optic layouts.

Key Points

• Prim algorithm finds a minimum spanning tree by growing it one edge at a time.
• It always picks the smallest edge connecting the tree to a new node.
• Works well on weighted, connected graphs.
• Useful for network design and cost minimization problems.

Key Takeaways

Prim algorithm builds a minimum spanning tree by adding the smallest connecting edge step-by-step.

It ensures all nodes are connected with the least total edge weight in a weighted graph.

Ideal for problems involving cost-efficient network or infrastructure design.

Starts from any node and grows the tree until all nodes are included.