Prim's Algorithm: Understanding Minimum Spanning Trees
Dr Arun Kumar
PhD (Computer Science) Introduction
 Definition
 Key Concepts
 Steps Overview
 Initialization
 Priority Queue
 Adding Edges
 Updating the Priority Queue
 Algorithm Termination
 Time Complexity
 Space Complexity
 Pseudocode
 Example
 Implementation in Python
 RealLife Example
 Context
 Applying Prim’s Algorithm
 Nodes and Edges Representation
 Graph Construction
 Initialization
 Priority Queue (MinHeap)
 Building the MST
 Completion
 Example Walkthrough
 Steps in Prim's Algorithm
 Conclusion
1. Introduction
Prim's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, undirected graph. The MST is a subset of the graph's edges that connects all vertices together without any cycles and with the minimum possible total edge weight.
2. Definition
Prim's Algorithm starts with a single vertex and grows the MST one edge at a time by adding the smallest edge that connects a vertex in the growing MST to a vertex outside of it.
3. Key Concepts
 Graph: A collection of vertices (nodes) and edges (links between nodes).
 Weighted Graph: Each edge in the graph has an associated weight (cost).
 Minimum Spanning Tree: A subset of edges forming a tree that includes all vertices with the minimum total edge weight.
4. Steps Overview
 Initialize the MST with a single vertex.
 While the MST does not include all vertices:
 Find the smallest edge connecting a vertex in the MST to a vertex outside.
 Add this edge to the MST.
 Repeat until all vertices are included.
5. Initialization
 Choose an arbitrary starting vertex.
 Initialize an empty MST and a set of visited vertices containing only the starting vertex.
6. Priority Queue
 Use a priority queue (minheap) to efficiently select the smallest edge.
 Initially, insert all edges from the starting vertex into the priority queue.
7. Adding Edges
 Extract the smallest edge from the priority queue.
 If the edge connects a visited vertex to an unvisited vertex, add it to the MST.
8. Updating the Priority Queue
 After adding an edge to the MST, add all edges from the newly visited vertex to the priority queue.
 Ensure edges connecting two visited vertices are not considered.
9. Algorithm Termination
 The algorithm terminates when all vertices are included in the MST.
 The result is the MST with the minimum total edge weight.
10. Time Complexity
 Using a priority queue with a binary heap, the time complexity is O(E log V), where E is the number of edges and V is the number of vertices.
11. Space Complexity
 The space complexity is O(V + E), accounting for the storage of the graph, the priority queue, and the MST.
12. Pseudocode
function primsAlgorithm(graph, startVertex):
MST = []
visited = set([startVertex])
priorityQueue = all edges from startVertex
while priorityQueue is not empty:
edge = priorityQueue.extractMin()
if edge connects visited to unvisited vertex:
add edge to MST
mark new vertex as visited
add all edges from new vertex to priorityQueue
return MST
13. Example
Consider a graph with vertices {A, B, C, D} and edges with weights:
 AB: 1
 AC: 3
 BC: 1
 BD: 6
 CD: 2
Starting from vertex A:
 Add edge AB (weight 1).
 Add edge BC (weight 1).
 Add edge CD (weight 2).
MST includes edges: {AB, BC, CD} with total weight 4.
14. Implementation in Python
import heapq
def prims_algorithm(graph, start):
mst = []
visited = set([start])
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 to_next, weight in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (weight, to, to_next))
return mst
graph = {
'A': {'B': 1, 'C': 3},
'B': {'A': 1, 'C': 1, 'D': 6},
'C': {'A': 3, 'B': 1, 'D': 2},
'D': {'B': 6, 'C': 2}
}
print(prims_algorithm(graph, 'A'))
Prim's Algorithm is widely applicable in various reallife scenarios where it's crucial to connect a set of points (or nodes) with the minimum total connection cost. Here’s a detailed reallife example:
RealLife Example: Designing an Electrical Circuit Layout
Context
Consider a company planning to design the layout of electrical wiring for a new office building. The goal is to connect various electrical outlets (nodes) with the minimum amount of wiring (edges) to ensure that every outlet is connected to the power supply while minimizing the cost of wiring.
Applying Prim’s Algorithm

Nodes and Edges Representation
 Nodes: Each electrical outlet and the main power source represent the nodes in the graph.
 Edges: The possible paths (wiring routes) between outlets and their respective distances (or wiring costs) represent the edges with weights.

Graph Construction
 A weighted, undirected graph is created where each edge weight corresponds to the cost or distance of the wiring between two outlets.

Initialization
 Choose an arbitrary starting outlet (node), typically the one nearest to the main power source.
 Initialize the MST with the starting outlet and mark it as visited.

Priority Queue (MinHeap)
 Use a priority queue to manage the edges connecting visited and unvisited nodes, prioritized by the least cost.

Building the MST
 Continuously select the smallest edge from the priority queue that connects a visited outlet to an unvisited one.
 Add this edge to the MST and mark the connected outlet as visited.
 Update the priority queue with new edges from the newly visited outlet.

Completion
 Repeat the process until all outlets are included in the MST, ensuring the entire office is wired with the minimum total wiring cost.
Example Walkthrough
Assume the office has four outlets (A, B, C, D) with the following wiring costs (distances):
 AB: $10
 AC: $20
 BC: $5
 BD: $15
 CD: $30
Steps in Prim's Algorithm:

Start from outlet A:
 Add edges AB ($10) and AC ($20) to the priority queue.

Select edge AB ($10):
 Add B to the MST, mark it as visited.
 Add edges BC ($5) and BD ($15) to the priority queue.

Select edge BC ($5):
 Add C to the MST, mark it as visited.
 Add edge CD ($30) to the priority queue.

Select edge BD ($15):
 Add D to the MST, mark it as visited.

Remaining Edges:
 Edge CD ($30) is ignored as it connects already visited nodes.
The resulting MST includes edges AB, BC, and BD with a total wiring cost of $30.
By applying Prim's Algorithm, the office building’s electrical wiring layout is designed efficiently with the minimum total wiring cost. This reallife application demonstrates how Prim's Algorithm can optimize the layout of physical connections, reducing both material and labor costs in construction and network design.
15. Conclusion
Prim's Algorithm is efficient for finding the MST in dense graphs. It incrementally builds the MST by always choosing the smallest edge that connects the growing tree to a new vertex. It is particularly useful in networking and circuit design where minimizing the total length of the connections is crucial.
Related Questions
What is the Prim's algorithm?
Prim's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) for a weighted undirected graph. It starts from an arbitrary node and grows the MST by repeatedly adding the shortest edge from the tree to a vertex not yet in the tree, until all vertices are included.
What is Kruskal and Prim's algorithm discuss?
Prim's and Kruskal's algorithms are both used to find the MST of a graph: Prim's Algorithm: Builds the MST starting from an arbitrary node and adding the shortest edge from the tree to a vertex not yet in the tree, until all vertices are included. Kruskal's Algorithm: Builds the MST by sorting all edges of the graph by their weight and adding them one by one to the MST if they do not form a cycle, until all vertices are included.
Is Prim's algorithm Dijkstra?
No, Prim's algorithm is not Dijkstra's algorithm, though they are similar. Prim's algorithm is used to find the MST, while Dijkstra's algorithm is used to find the shortest path from a single source to all other vertices in a weighted graph. Both algorithms use a priority queue and have similar structures, but their purposes are different.
Why Prim's algorithm is called greedy?
Prim's algorithm is called greedy because it makes a series of choices that are locally optimal (i.e., it always picks the shortest edge that connects a vertex in the MST to a vertex outside the MST) in the hope that these choices will lead to a globally optimal solution (the MST).
Is Prim's algorithm correct?
Yes, Prim's algorithm is correct. It produces a minimum spanning tree of a connected, weighted undirected graph. The correctness of the algorithm is ensured by the greedy choice property and the cut property.
What is the proof of Prim?
The proof of Prim's algorithm relies on the cut property of MSTs, which states that for any cut in the graph, the minimum weight edge crossing the cut is part of the MST. Prim's algorithm repeatedly finds and adds these minimum edges, ensuring that it always grows a tree in the MST.
What is the runtime of Prim's?
The runtime of Prim's algorithm depends on the data structures used: With an adjacency matrix and a simple linear search, the runtime is ๐ ( ๐ 2 ) O(V 2 ). With an adjacency list and a binary heap, the runtime is ๐ ( ๐ธ log โก ๐ ) O(ElogV). With an adjacency list and a Fibonacci heap, the runtime is ๐ ( ๐ธ + ๐ log โก ๐ ) O(E+VlogV).
Is Kruskal faster than Prim?
The relative performance of Kruskal's and Prim's algorithms depends on the specifics of the graph and the data structures used: For sparse graphs (where ๐ธ โ ๐ EโV), Prim's algorithm with a Fibonacci heap ( ๐ ( ๐ธ + ๐ log โก ๐ ) O(E+VlogV)) can be more efficient. For dense graphs, Kruskal's algorithm ( ๐ ( ๐ธ log โก ๐ธ ) O(ElogE)) may be faster. The actual performance can vary based on implementation details and the specific characteristics of the input graph.
Related Post
Research Design and Methodology in depth Tutorial
This guide provides an indepth overview of the essential aspects of research design and methodology.
How to Conduct a Literature Review in Research
This guide serves as a detailed roadmap for conducting a literature review, helping researchers navigate each stage of the process and ensuring a thorough and methodologically sound review.
How to Formulate and Test Hypotheses in Research
Hereโs a stepbystep guide, illustrated with an example, to help understand how to formulate and test hypotheses using statistics.
Difference between Qualitative and Quantitative Research with Example
Research methodologies can be broadly categorized into qualitative and quantitative approaches. This article explores these differences using an example, including the use of statistics.