Prims Algorithm

Prim’s algorithm is basically a greedy algorithm that is used to find the MST (Minimum Spanning Tree) for a directed or undirected graph. The MST is basically a subset of a graph G that has the lowest sum of weights, and it should connect all the vertices of the graph G.

Here are the steps of the prim’s algorithm: -

· Choose any random vertex and find adjacent of that vertex and take minimum of them.

· Find adjacency vertices of new vertex and take minimum of these adjacent and previous.

· Repeat step 2 until all the vertices are not covered.

Here’s an example:

Starting from 1 the MST(Minimum Spanning Tree) will be:

The MST weight for the following graph G starting at 1 will be 130.

Time Complexity:

The time complexity of Prim’s Algorithm is O((V+E)log V), where E is the Edge and V is the Vertex in the graph given. The time complexity is this because each vertex is inserted in the priority queue only once and insertion in priority queue take log time.

Prim’s Algorithm Applications:

General Applications:

1. Distances between the cities for the minimum route calculation for transportation.
2. For Establishing the network cables these play important role in finding the minimum cables required to cover the whole region

Computer Science Applications:

1. Used in AI(Artificial Intelligence)
2. Game Development

Here’s the implementation of the Prim’s Algorithm in Python:

import sys # Library for INT_MAX
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
# A utility function to print the constructed MST stored 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 utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minKey(self, key, mstSet):
# Initialize 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
# Function to construct and print MST for a graph
# represented using adjacency matrix representation
def primMST(self):
# Key values used to pick minimum weight edge in cut
key = [sys.maxsize] * self.V
parent = [None] * self.V # Array to store constructed MST
# Make key 0 so that this vertex is picked as first vertex
key[0] = 0
mstSet = [False] * self.V
parent[0] = -1 # First node is always the root of
for cout in range(self.V):
# Pick the minimum distance vertex from
# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.minKey(key, mstSet)
# Put the minimum distance vertex in
# the shortest path tree
mstSet[u] = True
# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for v in range(self.V):
# graph[u][v] is non zero only for adjacent vertices of m
# mstSet[v] is false for vertices not yet included in MST
# Update the key only if graph[u][v] is smaller than key[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)
g = Graph(5)
g.graph = [ [0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]
g.primMST();