Prim's Algorithm

Prim's Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) for a weighted, connected, and undirected graph. The algorithm builds the MST by starting from an arbitrary vertex and iteratively adding the smallest edge that connects a vertex in the tree to a vertex outside the tree.

1 Definition

Given a weighted, connected, undirected graph G = (V, E), Prim's Algorithm constructs a spanning tree T such that the total weight of the edges in T is minimized. At each step, the algorithm selects the edge with the lowest weight that connects a vertex in T to a vertex not yet in T.

2 Concept

Prim's Algorithm works on the following principles:

1. Initialization: Start with an arbitrary vertex; mark it as part of the MST.
2. Edge Selection: Among all edges that connect vertices in the MST to those not in the MST, select the edge with the smallest weight.
3. Expansion: Add the selected edge and the new vertex to the MST.
4. Repeat: Continue the process until all vertices are included in the MST.

3 Algorithm Steps

1. Initialize the MST with a starting vertex.
2. While the MST does not contain all vertices:
   • Find the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST.
   • Add the selected edge and the corresponding vertex to the MST.
3. End While

Example

Consider the following weighted graph:

Vertex Pair	Edge Weight
A - B	4
A - C	3
B - C	1
B - D	2
C - D	5

One possible execution of Prim's Algorithm starting at vertex A:

1. Start with vertex A.
2. The available edges are A - B (4) and A - C (3). Choose A - C (3) because 3 is the smallest.
3. Now the MST contains A and C. The available edges are A - B (4), C - B (1), and C - D (5). Choose C - B (1).
4. MST now contains A, C, and B. The remaining available edge is B - D (2) and C - D (5). Choose B - D (2).
5. The MST now includes all vertices with the edges A - C (3), C - B (1), and B - D (2). The total weight is 3 + 1 + 2 = 6.

Implementation

A simple implementation of Prim's Algorithm in Python:

import heapq

def prim_mst(graph, start):
    mst = []
    visited = set([start])
    # Priority queue: (edge_weight, from_vertex, to_vertex)
    edges = [(weight, start, to) for to, weight in graph[start].items()]
    heapq.heapify(edges)

    while edges:
        weight, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, weight))
            for next_to, next_weight in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_weight, to, next_to))
    return mst

# Example graph represented as an adjacency dictionary
graph = {
    'A': {'B': 4, 'C': 3},
    'B': {'A': 4, 'C': 1, 'D': 2},
    'C': {'A': 3, 'B': 1, 'D': 5},
    'D': {'B': 2, 'C': 5}
}

mst = prim_mst(graph, 'A')
print("Minimum Spanning Tree:", mst)

Advantages

• Greedy Approach – Always selects the smallest available edge.
• Efficient for Dense Graphs – Performs well when there are many edges.
• Simple Implementation – Easy to understand and implement.

Limitations

• Requires a Connected Graph – Prim's Algorithm works only on connected graphs.
• Potential for High Memory Usage – Maintaining a priority queue can require extra memory in very large graphs.

Applications

• Network Design – Used in designing efficient communication, transportation, or power networks.
• Cluster Analysis – Forms the basis for some hierarchical clustering techniques.
• Approximation Algorithms – Serves as a component in algorithms for solving NP-hard problems like the Traveling Salesman Problem.

See Also

• Minimum Spanning Tree
• Kruskal’s Algorithm
• Borůvka’s Algorithm
• Greedy Algorithm
• Graph Theory