Prim's Algorithm

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Prim's Algorithm

Table of Contents

Contents are not accessible

Prim’s algorithm is another popular method for finding the Minimum Spanning Tree (MST) of a connected, undirected graph. Unlike Kruskal's algorithm, which adds the smallest edge regardless of the current MST, Prim’s algorithm builds the MST by always adding the smallest edge that extends the growing tree. It starts with a single vertex and expands the MST one edge at a time by selecting the smallest edge that connects a vertex in the MST to a vertex outside the MST.

Goal: Connect all vertices in the graph with the minimum total edge weight without forming cycles.
Process:
- Start with a single vertex: Begin with any arbitrary vertex as the starting point.
- Expand the MST: Repeatedly add the smallest edge that connects a vertex in the MST to a vertex outside the MST.
Priority Queue: Prim’s algorithm efficiently selects the smallest edge using a priority queue (min-heap), ensuring that the edge with the minimum weight is always chosen next.
Greedy Approach: Like Kruskal's algorithm, Prim's algorithm follows a greedy strategy, making the locally optimal choice at each step with the hope of finding the global optimum.

Overall, Prim's algorithm ensures that the final MST connects all vertices with the least total weight, making it suitable for network design, clustering, and other applications where optimal connectivity is required. It is particularly efficient for dense graphs due to its ability to directly expand the MST from the growing tree.

Step-by-Step Algorithm

Initialize: Create a boolean array inMST[] to keep track of vertices included in the MST. Initialize all vertices as not included.
Start with an Arbitrary Vertex: Select any vertex as the starting point (e.g., vertex 0).
Insert Edges: Insert all edges from the starting vertex into a priority queue (min-heap).
Loop Until MST is Complete:
- Extract the edge with the minimum weight from the priority queue.
- If the destination vertex of the edge is not already included in the MST:
  - Include the edge in the MST.
  - Mark the destination vertex as included in the MST.
  - Insert all edges from the newly included vertex into the priority queue.
Repeat step 4 until all vertices are included in the MST.

Algorithm Walkthrough

Consider the example used in the code with the following edges and weights:

Edges: (0-1, 0-2, 0-3, 1-3, 2-3)
Weights: 10, 6, 5, 15, 4
Vertices: 4 (0, 1, 2, 3)

Initialize:
```
inMST[] = [false, false, false, false]
```

Start with Vertex 0:

Insert edges (0-1, 10), (0-2, 6), and (0-3, 5) into the priority queue.

Priority Queue:

Priority Queue: [(0-3, 5), (0-2, 6), (0-1, 10)]

Loop:
- Extract (0-3, 5):
  - Include edge (0-3) in MST.
  - Mark vertex 3 as included in MST.
  - Insert edges (3-1, 15) and (3-2, 4) into the priority queue.
```
MST: [(0-3, 5)]
inMST[] = [true, false, false, true]
Priority Queue: [(3-2, 4), (0-2, 6), (0-1, 10), (3-1, 15)]
```
- Extract (3-2, 4):
  - Include edge (3-2) in MST.
  - Mark vertex 2 as included in MST.
  - Insert edges (2-0, 6) and (2-3, 4) into the priority queue (but only if they lead to vertices not in MST).
```
MST: [(0-3, 5), (3-2, 4)]
inMST[] = [true, false, true, true]
Priority Queue: [(0-2, 6), (0-1, 10), (3-1, 15)]
```
- Extract (0-2, 6):
  - Vertex 2 is already in MST, so skip this edge.
```
Priority Queue: [(0-1, 10), (3-1, 15)]
```
- Extract (0-1, 10):
  - Include edge (0-1) in MST.
  - Mark vertex 1 as included in MST.
  - Insert edges (1-0, 10) and (1-3, 15) into the priority queue (but only if they lead to vertices not in MST).
```
MST: [(0-3, 5), (3-2, 4), (0-1, 10)]
inMST[] = [true, true, true, true]
Priority Queue: [(3-1, 15)]
```
- Extract (3-1, 15):
  - Vertex 1 is already in MST, so skip this edge.
```
Priority Queue: []
```
Final MST:
```
Edges: (0-3, 5), (3-2, 4), (0-1, 10)
```

Code

Python3

. . . .

Complexity Analysis

Time Complexity

Priority Queue Operations: Each insertion and extraction from the priority queue takes $O(\log V)$ time.
Edge Processing: Each edge is processed once, leading to $O(E \log V)$ time complexity, where (E) is the number of edges and (V) is the number of vertices.

Thus, the overall time complexity of Prim's algorithm is $O(E \log V)$ .

Space Complexity

Priority Queue: Storing up to (E) edges in the priority queue requires $O(E)$ space.

Thus, the overall space complexity is $O(E)$ .

Difference Between Kruskal's and Prim's Algorithm

Feature	Kruskal's Algorithm	Prim's Algorithm
Approach	Greedy approach, considers edges in ascending order of weight.	Greedy approach, builds the MST by growing one vertex at a time.
Starting Point	Can start from any edge.	Starts from any arbitrary vertex.
Graph Representation	Works well with edge list representation.	Works well with adjacency matrix or adjacency list.
Data Structure Used	Uses Union-Find data structure to detect cycles.	Uses a priority queue (min-heap) to pick the smallest edge.
Edge Selection	Selects the smallest edge that doesn't form a cycle.	Selects the smallest edge that extends the growing MST.
Cycle Detection	Explicit cycle detection using Union-Find.	Implicit cycle detection, as it only extends the MST.
Efficiency	More efficient for sparse graphs with fewer edges.	More efficient for dense graphs with more edges.
Time Complexity	$O(E \log E)$ , where (E) is the number of edges.	$O(E \log V)$ , where (E) is the number of edges and (V) is the number of vertices.
Space Complexity	$O(E + V)$ for storing edges and Union-Find structure.	$O(V^2)$ for adjacency matrix or $O(V + E)$ for adjacency list with a priority queue.
Parallelism	Difficult to parallelize due to the sequential nature of edge selection.	More suitable for parallel processing since multiple vertices can be processed simultaneously.
Usage	Suitable for connected, undirected graphs.	Suitable for connected, undirected graphs.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible