Prim’s Minimum Spanning Tree

What is Minimum Spanning Tree?

The weights of all the edges in the tree are added to determine the cost of the spanning tree. Many spanning trees may exist. The spanning tree with the lowest cost among all other spanning trees is known as a minimum spanning tree. There may be a lot of minimum spanning trees as well.

How does Prim’s Algorithm Work?

• Initialization: Start with any node and mark it as part of the Minimum Spanning Tree (MST).
   
• Priority Queue: Add edges connecting the node to all its adjacent nodes to a priority queue (or any suitable structure), with the edge weight as the priority.
   
• Choose Minimum Edge: Extract the minimum-weight edge from the queue and mark the connected vertex as part of the MST.
   
• Update Queue: Add edges from the newly added node that connect to unvisited nodes into the queue.
   
• Repeat: Continue the process until all nodes are included in the MST.
   
• Result: The algorithm stops when all nodes are part of the MST, and the tree is constructed with the minimum sum of edge weights.

Illustration of Prim's Algorithm

In the undirected graph provided (first image), the vertices are labeled from 1 to 5, and edges between them have weights, like 1 → 2 with a weight of 2 and 3 → 5 with a weight of 10.
 

1. Initial Vertex Selection: Suppose we begin from vertex 1. Among the connecting edges, the smallest weight edge (1 → 2 with weight 2) is chosen.
    
2. Expand the Tree: Now, the algorithm adds the next smallest edge from the current MST. From vertex 2, the smallest edge is (2 → 5 with weight 3).
    
3. Continue Adding Minimum Edges: The process continues, adding edge (5 → 4 with weight 5), and then edge (4 → 3 with weight 2).
    
4. Final Tree: The graph forms the Minimum Spanning Tree as shown in the third image, with a total weight of 12 (2 + 3 + 5 + 2).
    

This tree connects all vertices while minimizing the overall edge cost.

Algorithm

To find the minimum spanning tree of the undirected graph, we can use two algorithms, i.e., Kruskal's and Prim’s algorithms. In this article, we will be learning about Prim’s algorithm.

Prim’s Algorithm

The Greedy technique is used by Prim's Algorithm to discover the minimum spanning tree. In Prim's Algorithm, the spanning tree is grown from scratch. We add a vertex to the expanding spanning tree in Prim's method rather than an edge in Kruskal's.

Steps of the algorithm

• Keep two separate sets of vertices. One of them has vertices in the expanding spanning tree, and the other does not have any such vertices.
   
• Choose the least expensive vertex that is connected to the developing spanning tree but isn't already present in the growing spanning tree, and include it there. Priority Queues can be used to accomplish this. Add the developing spanning tree's connected vertices to the Priority Queue.
   
• Examine for cycles. To accomplish this, mark the nodes that have already been chosen and only add the unmarked nodes to the Priority Queue.
   

Following are the steps (working of Prim’s algorithm):

Implementation

Implementation in C++, Python

• C++
• Python

C++

#include <bits/stdc++.h>
using namespace std;

// Defining number of vertices
#define V 5

/* a utility function that searches the set of vertices not yet included in MST for the vertex with the lowest key value. */
int minKey(int key[], bool mstSet[])
{
	// Initializing the min value
	int min = INT_MAX, min_index;

	for (int v = 0; v < V; v++)
		if (mstSet[v] == false && key[v] < min)
			min = key[v], min_index = v;

	return min_index;
}

/* A useful function to print the built-in MST contained in parent[] */
void printMST(int parent[], int graph[V][V])
{
	cout << "Edge \tWeight\n";
	for (int i = 1; i < V; i++)
		cout << parent[i] << " - " << i << " \t"
		<< graph[i][parent[i]] << " \n";
}

/* For a graph represented using adjacency matrix representation, there is a function to construct and print MST. */
void primMST(int graph[V][V])
{
	// array that stores MST
	int parent[V];

	// Key factors utilised to select the cut's minimal weight
	int key[V];

	// to display a collection of vertices used in MST
	bool mstSet[V];

	// Set all keys to INFINITE at start.
	for (int i = 0; i < V; i++)
		key[i] = INT_MAX, mstSet[i] = false;

/* Include the initial vertex in MST at all times. To ensure that this vertex is chosen as the initial vertex, set key to 0. */
	key[0] = 0;
	parent[0] = -1; // In MST first node is always root

	// The MST of V vertices
	for (int count = 0; count < V - 1; count++) {
        /* Choose the minimum key vertex from the collection of vertices that aren't yet part of MST. */
		int u = minKey(key, mstSet);

	// adding picked vertex to MST
	mstSet[u] = true;

/* Update the neighbouring vertices' parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST */
	for (int v = 0; v < V; v++)
/* Only the nearby vertices of m mst make graph[u][v] non zero. For vertices not yet included in MST, Set[v] is false. Only change the key if graph[u][v] is less than key[v]. */
		if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
			parent[v] = u, key[v] = graph[u][v];
	}

// printing the MST
	printMST(parent, graph);
}

// main code
int main()
{
	int graph[V][V] = { { 0, 1, 0, 0, 3 },
	{ 1, 0, 7, 0, 2 },
	{ 0, 7, 0, 2, 10 },
	{ 0, 0, 2, 0, 5 },
	{ 3, 2, 10, 5, 0 } };

	// printing the solution
	primMST(graph);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

import sys 
class Graph():

def __init__(self, vertices):
	self.V = vertices
	self.graph = [[0 for column in range(vertices)]
		for row in range(vertices)]

    # A useful function to print the built-in MST contained in parent[]
def printMST(self, parent):
	print("Edge \tWeight")
	for i in range(1, self.V):
		print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

""" A useful function that searches the set of vertices not yet included in the shortest path tree for the vertex with the lowest distance value. """
def minKey(self, key, mstSet):

	# Initializing the min value
	min = sys.maxsize

	for v in range(self.V):
		if key[v] < min and mstSet[v] == False:
			min = key[v]
			min_index = v

	return min_index

def primMST(self):

	key = [sys.maxsize] * self.V
	parent = [None] * self.V # array for storing MST

	key[0] = 0
	mstSet = [False] * self.V

	parent[0] = -1 # First node is always the root of MST

	for cout in range(self.V):

		"""Choose the minimum key vertex from the collection of vertices that aren't yet part of MST."""
		u = self.minKey(key, mstSet)

	# adding picked vertex to MST
	mstSet[u] = True

	""" Update the neighbouring vertices' parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST"""
	for v in range(self.V):

		if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
			key[v] = self.graph[u][v]
			parent[v] = u

	self.printMST(parent)


# Driver's code
if __name__ == '__main__':
	g = Graph(5)
	g.graph = [[ 0, 1, 0, 0, 3 ], 
              	[ 1, 0, 7, 0, 2 ], 
              	[ 0, 7, 0, 2, 10 ], 
              	[ 0, 0, 2, 0, 5 ], 
              	[ 3, 2, 10, 5, 0 ] ]
	g.primMST()

You can also try this code with Online Python Compiler

Run Code

Output

Edge  Weight
0 - 1   1 
3 - 2   2 
4 - 3   5 
1 - 4   2 

Complexity

Time Complexity O(V²): The time complexity of Prim's algorithm can be decreased to O(E log V) with the use of a binary heap if the input graph is represented using an adjacency list. In this implementation, the spanning tree is always believed to begin at the graph's root.

Space Complexity: O(V)
Check out this problem - No of Spanning Trees in a Graph

Advantages

• Efficiency: Prim's Algorithm is efficient for dense graphs, as it works well with the adjacency matrix.
   
• Simplicity: The algorithm is relatively easy to understand and implement, making it a popular choice in educational settings.
   
• Guaranteed Minimum Spanning Tree: It ensures the generation of a Minimum Spanning Tree, which is crucial in network design.
   
• Incremental Approach: The algorithm can be implemented incrementally, allowing for efficient updates when new edges are added.

Disadvantages

• Performance with Sparse Graphs: Prim's Algorithm may not perform as efficiently on sparse graphs compared to Kruskal's Algorithm.
   
• Memory Usage: The need to maintain an adjacency matrix can lead to high memory usage for large graphs.
   
• Complexity in Implementation: While simple in concept, the implementation can become complex in the case of certain data structures.
   
• Non-Optimal for Dynamic Graphs: The algorithm does not handle dynamic graphs effectively, where edges and vertices can change frequently.

Frequently Asked Questions

What are the properties of a spanning tree?

There is exactly the same number of edges and vertices in each of a graph's potential spanning trees. A cycle can never be found inside a spanning tree. If we remove one edge from the spanning tree, it will become unconnected since spanning trees are always minimally linked.

Why Prim's algorithm is greedy?

Input is rearranged by Prim's Algorithm in order to select the least expensive edge. In the sense that the algorithm strives to readjust the input to its own convenience at each iteration, we refer to Prim's Algorithm as an adaptive greedy algorithm.

Why is Prims better than Kruskal?

Prim's algorithm has an advantage over Kruskal's in that it is more complex. Prim's approach is therefore useful for handling dense networks with a large number of edges. However, when numerous edges with the same weight occur, Prim's approach doesn't provide us much control over the selected edges.

Which is faster Prim or Kruskal?

The Prim algorithm returns connected components and solely utilizes connected graphs. In dense graphs, Prim's method operates more quickly. In sparse graphs, Kruskal's algorithm operates more quickly.

Conclusion

In the above article, we have discussed about Spanning Tree. We looked at its algorithms with illustration how prims algorithms works. We also discussed about how to find spanning tree using Prim’s algorithm. We later in the end learned about an example of Prim’s algorithm and implementation of Prim’s algorithm. 

If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder Traversal, Regular and Bipartite graphs, and Planar and Non-Planar Graphs.

Happy Coding!