Prim’s Algorithm and Minimum Spanning Trees
In our everyday life, we use things that are based on the concept of Graphs. Two great examples are Social media and Google Maps. They are based on the concept of graphs. Now what do we mean by graphs in terms of Computer Science Engineering. A graph is a non-linear data structure that consists of edges connecting the vertices. Vertices are also called the Nodes. There are two types of edges, namely “Directed” and “Undirected”.
Directed edge ( → / ←) points to some other vertex while Undirected edge (— ) doesn’t point to any vertex.
A graph is denoted as G = {V,E} where ‘V’ is the Vertex and ‘E’ is the Edge.
Facebook uses various Vertex as the users and the various Edges to define the relations or connections between the users. Google Maps uses Vertex as the location or the destination and edges as the path to go between the places.
We require algorithms for the traversal of the graphs. Suppose you want to go from one vertex of the graph to the other vertex in least possible time or cost, how will you approach to that problem?
The answer to this problem is the Minimum Spanning Tree.
Now what is Minimum Spanning Tree?
So before knowing what is Minimum Spanning Tree, let us see what is a Tree and what is the difference between a Tree and a Graph.
We have already seen what is a graph. There can be any number of edges between the vertices in a graph and cycle may/may not exist in a Graph data structure. While, a tree is also a graph but without any cycle present in it.
Minimum Spanning Tree (MST): It is also called Minimum Weight Spanning Tree because for selecting the edges, we select the “Minimum Weighted Edge”. The main assumption for MST is that the edges should be undirected. Creation for MST using Prim’s Algorithm is not possible in case of directed edge because you can’t reach from one node to every other node, even if they are connected. You can see the example (fig.) shown below.
Here the Vertex 3 has 3 incoming edges while it has no outgoing edge (Outgoing edges are Zero). So, from Vertex 3 you can’t go to any other vertex. Hence, you can’t create a MST.
So how does the Prim’s Algorithm work?
Prim’s is a simple algorithm that helps us in creating a Minimum Spanning Tree from the given undirected graph. We take the edges of minimum weights in order to create a Minimum Spanning Tree. If we have to create a unique MST for a given graph, all the weights should be unique. If two or more edges have the same weight, then there is a chance that multiple MST’s can be created for that graph.
Prim’s algorithm for MST:
1. To keep track of vertices already included in the MST, create a set MSTSET.
2. In the input graph, assign a key value to all the vertices. Initialize all the key values as ‘Infinite’. In order to get picked first, assign key value -> 0 for the first vertex.
3. While the MSTSET does not include all the vertices
(i) Pick any vertex ‘U’ which is absent in MSTSET and has the minimum key value.
(ii) Include ‘U’ to MSTSET.
(iii) Update the key values of all the adjacent vertices U. In order to update the key values, iterate through all the adjacent vertices. For each adjacent vertex ‘V’, if weight of edge ‘U-V’ is less than the previous key value of ‘V’, update the value of key as weight of ‘U-V’.
Did you enjoy this blog ? Do inform me -
Utkarsh Mishra
utkarshmishra7007@gmail.com