Algorithm Deep Dive Prim's Algorithm

Prim's Minimum Spanning Tree Algorithm

4 min read

Prim’s algorithm is a graph-based algorithm used to construct a Minimum Spanning Tree (MST) for a given weighted, undirected graph. It builds the MST by greedily selecting the lowest-weight edge that connects a vertex in the growing MST to a vertex outside it. Prim’s algorithm maintains a priority queue to efficiently select the next minimum-weight edge, ensuring that at each step, it chooses the cheapest way to expand the MST without creating cycles. This process continues until all vertices are included in the MST.

Prim’s algorithm is a greedy algorithm, meaning it always chooses the cheapest edge at each step, without considering the long-term consequences of its choices. Despite its simplicity, Prim’s algorithm is proven to be efficient and effective in finding the MST of a weighted, connected graph.

What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices together with the minimum possible total edge weight. In other words, it is the cheapest or minimum cost subgraph in a given graph that connects all the nodes in the graph.

For example, for the undirected weighted graph shown below:

3
3
8
8
4
4
A
A
3
3
4
4
C
C
F
F
2
2
E
E
B
B
3
3
8
8
D
D
3
3Text is not SVG - cannot display

Below is how the minimum spanning tree looks like:

3
3
A
A
3
3
C
C
F
F
2
2
E
E
B
B
3
3
D
D
3
3Text is not SVG - cannot display

Refer to this article to learn more about Minimum Spanning Trees.

Detailed Steps of Prim’s MST Algorithm

Prim’s algorithm builds the MST incrementally, starting with a single vertex and expanding the tree by adding the cheapest possible edge from the tree to a vertex not yet in the tree. It maintains a growing set of vertices that are part of the MST and continuously adds the smallest weight edge that connects a vertex in the MST to a vertex outside the MST.

Step-by-step process of Prim’s algorithm:

  1. Initialization:

    • Select an arbitrary vertex to start the MST. This vertex is the initial member of the MST set.
    • Initialize a set to keep track of vertices included in the MST.
    • Create an array to store the minimum cost edge that connects each vertex to the growing MST. Initialize the starting vertex’s cost to zero and others to infinity.
    • Use a priority queue (or a min-heap) to store unused edges connected to the current MST.

  2. Growing the MST:

    • While the MST set does not contain all the vertices:
      • Select and remove the minimum-weight edge from the priority queue.
      • If the edge connects to a vertex already in the MST, discard it and continue.
      • Otherwise, add this edge to the MST and the new vertex to the MST set.
      • For each adjacent vertex of the extracted vertex, if the vertex is not yet in the MST, add the edge to priority queue.

  3. Termination:

    • The process continues until all vertices are included in the MST set.

The use of a priority queue allows for efficient selection of the minimum-weight edge at each step. If priority queue is not used, we would need to sort all edges every time a new edge is added.

Implementation

Loading code…

Time and Space Complexity

Time Complexity:

The time complexity of Prim’s algorithm depends on how dense the graph is and the data structure used to store and retrieve available edges. The most common implementation uses a priority queue (e.g., a min-heap) to efficiently select the next vertex to add to the MST. With a priority queue, the time complexity of Prim’s algorithm is O(E log V), where E is the number of edges in the graph and V is the number of vertices in the graph.

This is because the algorithm needs to:

  • Inserting each vertex into the priority queue takes O(log V) per edge. Note: Although the heap/priority queue size can grow to V * V-1 if each node in the graph has a link to every other node in the graph, the heap operation takes O(log V^2) which is 2*O(log V) which in turn can be approximated to O(log V).
  • Similarly, extracting the minimum-weight vertex from the priority queue takes O(log V) per extraction

The algorithm performs these operations for a maximum of E times, resulting in the overall time complexity of O(E log V).

Space Complexity:

The space complexity of Prim’s algorithm is O(E + V), as the algorithm needs to store the following data structures:

  • A priority queue to keep track of the vertices and their weights which can take a maximum of O(V) space
  • A set or array to keep track of the vertices that have already been added to the MST which takes O(V) space

Therefore, the overall space complexity of Prim’s algorithm is O(E + V).