Prims Algorithm
we can examine what is the minimal spanning tree and how to convert a graph right into a minimal spanning tree the use of Prim’s algorithm. we are able to examine the set of rules and python code for prim’s algorithm and an example for better information. finally, we will study the jogging time complexity and applications of prim’s algorithm in actual existence.
Prim’s algorithm is a greedy algorithm used to find the minimum spanning tree (MST) for a directed or undirected graph. Basically, MST is a subset of a graph G that hast the lowest sum of weights, and it should connect all the Vertices of the graph G.
The algorithm follows the bellow steps :-
- 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.
example:
the algorithm’s MST(minimum spanning tree) starting from 1 will be:
the weight for the above graph starting at 1 will b 130
Minimum Spanning Tree:
As we all recognise, the graph which does no longer have edges pointing to any direction in a graph is called an undirected graph and the graph constantly has a direction from a vertex to every other vertex. A spanning tree is a subgraph of the undirected linked graph where it consists of all the nodes of the graph with the minimal possible wide variety of edges. recollect, the subgraph should comprise each and every node of the original graph. If any node is ignored out then it isn’t always a spanning tree and additionally, the spanning tree doesn’t include cycles. If the graph has n range of nodes, then the overall range of spanning bushes produced from a whole graph is equal to n^(n-2). In a spanning tree, the edges might also or may not have weights related to them. consequently, the spanning tree wherein the sum of edges is minimum as possible then that spanning tree is referred to as the minimum spanning tree. One graph can have multiple spanning-tree but it could have simplest one particular minimal spanning tree. There are two one of a kind ways to discover the minimum spanning tree from the whole graph i.e Kruskal’s algorithm and Prim’s set of rules. let us study prim’s set of rules in element beneath:
Time Complexity:
Time complexity for Prim’s Algorithm is O((V+E)log V), here V is the Vertex and E is the Edge. The time complexity is such because each vertex is inserted in the priority queue only once and insertion in priority takes log time.
algorithm’s applications
general:
- Distances between the cities for the minimum route calculation for transportation.
- For Establishing the network cables these play important role in finding the minimum cables required to cover the whole region.
- It is used in network cycles and rail tracks connecting all the cities.
- It is used in cluster analysis.
computer science applications:
- Used in AI(Artificial Intelligence)
- Game Development
to further make the algorithm understandable below is an implementation of prims algorithm in python:
def prims_mst(self):
# Defining a really big number, that'll always be the highest weight in comparisons
postitive_inf = float('inf')# This is a list showing which nodes are already selected
# so we don't pick the same node twice and we can actually know when stop looking
selected_nodes = [False for node in range(self.m_num_of_nodes)]# Matrix of the resulting MST
result = [[0 for column in range(self.m_num_of_nodes)]
for row in range(self.m_num_of_nodes)]
indx = 0
# While there are nodes that are not included in the MST, keep looking:
while(False in selected_nodes):
# We use the big number we created before as the possible minimum weight
minimum = postitive_inf# The starting node
start = 0# The ending node
end = 0for i in range(self.m_num_of_nodes):
# If the node is part of the MST, look its relationships
if selected_nodes[i]:
for j in range(self.m_num_of_nodes):
# If the analyzed node have a path to the ending node AND its not included in the MST (to avoid cycles)
if (not selected_nodes[j] and self.m_graph[i][j]>0):
# If the weight path analized is less than the minimum of the MST
if self.m_graph[i][j] < minimum:
# Defines the new minimum weight, the starting vertex and the ending vertex
minimum = self.m_graph[i][j]
start, end = i, j
# Since we added the ending vertex to the MST, it's already selected:
selected_nodes[end] = True# Filling the MST Adjacency Matrix fields:
result[start][end] = minimum
if minimum == postitive_inf:
result[start][end] = 0indx += 1
result[end][start] = result[start][end]# Print the resulting MST
# for node1, node2, weight in result:
for i in range(len(result)):
for j in range(0+i, len(result)):
if result[i][j] != 0:
print("%d - %d: %d" % (i, j, result[i][j]))
Conclusion:
As we studied, the minimum spanning tree has its personal importance in the real world, it is critical to examine the prim’s set of rules which leads us to find the solution to many issues. on the subject of finding the minimum spanning tree for the dense graphs, prim’s set of rules is the primary choice.