PRIM’s Algorithm

The algorithm is based on the principle of greediness and guarantee finding the minimum
spanning tree of a graph in an efficient way. Prim's algorithm is used to find the minimum
spanning tree of a weighted undirected graph. The algorithm works by starting at a single
vertex and gradually building up the spanning tree by adding edges one at a time. At each step,
it selects the edge with the smallest weight that connects a vertex in the tree to a vertex outside
the tree. This process is repeated until all vertices are included in the tree.
Steps of Prim’s Algorithm
1. Initialize the MST with a starting vertex (arbitrarily chosen).
2. Select the minimum-weight edge that connects a vertex in the MST to a vertex outside
the MST.
3. Add the selected edge and the new vertex to the MST.
4. Repeat the process until all vertices are included in the MST.
Data Structures Used in Prim’s Algorithm
To efficiently implement Prim’s Algorithm, the following data structures are used:
• Priority Queue (Min-Heap): To store the edges sorted by minimum weight.
• Adjacency Matrix or Adjacency List: To store the graph representation.
• Visited Array: To track which nodes have been included in the MST.
Time Complexity Analysis
• Using an Adjacency Matrix and a linear search for the minimum key: O(V²)
• Using an Adjacency List and a Min-Heap (Priority Queue): O(E log V) (more
efficient for sparse graphs)

Key Concepts Used in Implementation

1. Greedy Strategy: Always picking the lowest-cost option to expand the tree.
2. Graph Representation:
o Adjacency Matrix (for dense graphs)
o Adjacency List (for sparse graphs, more memory-efficient)
3. Heap/Priority Queue: To efficiently get the next minimum edge.
4. Cycle Prevention: Ensuring no cycles form while constructing the MST.
Here's a step-by-step breakdown of Prim's algorithm:
 1. Choose an arbitrary vertex to start the tree.
2. Initialize a set T containing only the starting vertex. This set will eventually contain the
minimum spanning tree.
3. Initialize a priority queue Q containing all the edges connected to the starting vertex,
sorted by their weight.
4. While Q is not empty:
5. Remove the edge with the smallest weight from Q.
6. If the edge connects a vertex in T to a vertex, not in T, add the edge to T and add all the
edges connected to the new vertex to Q.

Implementation
C++ Language Concepts Adopted in the Program
This program implements Prim's algorithm to find the Minimum Cost Spanning Tree
(MST) of a given undirected weighted graph using a priority queue (min-heap).
1. Standard Template Library (STL)
• In C++, the statement typedef pair<int, int> pii; is used to create an alias for the data
type pair<int, int>. Here's what it does:

Explanation:

• pair<int, int>: This is a standard template in C++ from the <utility> header. It
is used to store a pair of values, where the first value is of type int and the second
is also of type int.
• typedef ... pii;: This creates a shorthand name (pii) for the type pair<int, int>.
Now, instead of writing pair<int, int> every time, you can simply write pii.

• vector<vector<pii>> adj;
o Uses STL vector to represent the adjacency list of the graph.
o typedef pair<int, int> pii; defines pii as a shortcut for pair<int, int>, used
to store edges (neighbor, weight).
• priority_queue<pii, vector<pii>, greater<pii>> pq;
o Uses priority queue to implement a min-heap that helps select the edge with
the minimum weight.

o pair<int, int>: The data type stored in the priority queue is a pair of integers.
Each element is of the form {first, second}.
o vector<pair<int, int>>: This specifies the underlying container for the priority
queue. In C++, priority queues are typically implemented using a vector.
o greater<pair<int, int>>: This sets the comparison function. By default,
priority_queue is a max-heap, but by using greater, it becomes a min-heap,
where the smallest element is at the top.
 o pq: This is the name of the priority queue
2. Greedy Algorithm
• Prim’s Algorithm follows a greedy approach, always picking the smallest available
edge to grow the MST.
3. Graph Representation
• The adjacency list (vector<vector<pii>> adj) stores graph edges in a memory-
efficient way.
4. Boolean Array for Tracking Visited Nodes
• vector<bool> visited;:
o Keeps track of which nodes have already been included in the MST.
5. Pairing and Sorting Mechanism
• make_pair(w, u):
o Creates a pair (weight, vertex) for efficient edge selection.
• greater<pii> in priority_queue:
o Ensures that the smallest weight edge is always at the top.
6. Iteration Using Range-Based Loops
• for (auto& v : adj[u]) { ... }:
o Iterates over the adjacency list to process all edges connected to a node.
7. Object-Oriented Programming (OOP) Concept
• The program does not explicitly use classes, but it follows modularity by
separating the prim function from main.
Priority Queue: Priority queue is the extension of the queue in which elements associated with
priority and elements having higher priority is popped first. Priority queue can contain elements
with various data types such as integer, pair of integers, custom data type. But one thing is
common that there is one element that defines the priority of the element. Therefore, the
Priority queue of pairs can have two types of ordering –
1. Ordered by the first element of pair
2. Ordered by the second element of pair

Priority Queue ordered by first element (Min)

In C++ if the element is in the form of pairs, then by default the priority of the elements is
dependent upon the first element. By default priority queues are max heaps. Therefore, we just
have to use the priority queue of pairs with greater<> function object.
 priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>> > g

Vectors: Vectors are known as dynamic arrays which can change its size automatically when
an element is inserted or deleted. This storage is maintained by container.
vector::resize()
The function alters the container’s content in actual by inserting or deleting the elements from
it. It happens so,

1. If the given value of n is less than the size at present then extra elements are demolished.
2. If n is more than current size of container then upcoming elements are appended at the
end of the vector.
Syntax:
vectorname.resize(int n, int val)

Tracing of Prim’s Algorithm

We have 5 vertices (0 to 4) and the following weighted edges:

Step 1: Initialization
• The adjacency list is set up as per the given graph structure.
• The visited array is initialized as [false, false, false, false, false].
• A min-heap (priority queue) is initialized and the algorithm starts at vertex 0.
Step 2: Iteration Details
Step 3: Final MST Output
• The edges forming the Minimum Spanning Tree (MST):

• Total MST Weight = 16.

Conclusion
• The algorithm successfully selects edges with minimum weight while avoiding
cycles.
• The priority_queue ensures that the smallest edge is always chosen first.
• The final output:
• 0 ---> 1 [Weight: 2]
 • 1 ---> 2 [Weight: 3]
• 1 ---> 4 [Weight: 5]
• 0 ---> 3 [Weight: 6]
• Minimum spanning tree weight: 16

Source code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii;

vector<vector<pii>> adj; // adjacency list of the graph
vector<bool> visited; // visited array to keep track of visited vertices

int prim(int start) {

int n = adj.size();
int mstWeight = 0;
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;

// priority queue to select the next edge to add to the MST

pq.push({0, {start, -1}}); // start from the given vertex with weight 0 and no parent

while (!pq.empty()) {
int u = pq.top().second.first; // current vertex
int parent = pq.top().second.second; // parent vertex
int w = pq.top().first; // weight of the edge
pq.pop();

if (visited[u]) continue; // skip visited vertices

visited[u] = true;
mstWeight += w;

// Display the edge with its weight

if (parent != -1) { // Ignore the starting node
cout << parent << " ---> " << u << " [Weight: " << w << "]" << endl;
}

// Add all connected edges to the priority queue

for (auto& v : adj[u]) {
 if (!visited[v.first]) {
pq.push({v.second, {v.first, u}});
}
}
}
return mstWeight;
}

int main() {
// Define the graph
adj.resize(5); // 5 vertices

// Graph edges (undirected, weighted)

adj[0].push_back({1, 2});
adj[0].push_back({3, 6});

adj[1].push_back({0, 2});
adj[1].push_back({2, 3});
adj[1].push_back({4, 5});
adj[1].push_back({3,8});

adj[2].push_back({1, 3});
adj[2].push_back({4, 7});

adj[3].push_back({0, 6});
adj[3].push_back({4, 9});
adj[3].push_back({1,8});

adj[4].push_back({1, 5});
adj[4].push_back({2, 7});
adj[4].push_back({3, 9});

visited.resize(5, false); // set all vertices as unvisited

// Find the MST starting from vertex 0

int mstWeight = prim(0);

cout << "Minimum spanning tree weight: " << mstWeight << endl;
return 0;
}
Output:

0 ---> 1 [Weight: 2]
1 ---> 2 [Weight: 3]
1 ---> 4 [Weight: 5]
0 ---> 3 [Weight: 6]
Minimum spanning tree weight: 16