Last Updated: 17 Jan, 2021
Prim's MST
Moderate
Asked in company
You are given an undirected connected weighted graph having ‘N’ nodes numbered from 1 to 'N'. A matrix ‘E’ of size M x 2 is given which represents the ‘M’ edges such that there is an edge directed from node E[i][0] to node E[i][1]. You are supposed to return the minimum spanning tree where you need to return weight for each edge in the MST.
For example :
The MST (Minimum Spanning Tree) for the above graph is:
Input Format :
The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows.
The first line of each test case argument given is an integer ‘N’ representing the number of nodes in the graph.
The second line of each test case contains a given integer ‘M’ representing the number of edges.
The next ‘M’ lines in each test case contain a matrix ‘E’ of size M x 2 which represents the ‘M’ edges such that there is an edge directed from node E[i][0] to node E[i][1].
Output Format :
For each test case, print the minimum spanning tree in the form of edges and their weights which are included in the MST.
Note :
You do not need to print anything; It has already been taken care of.
Constraints :
1 ≤ T ≤ 5
2 <= N <= 100
1 <= M <= min(1000, N(N - 1) / 2)
1 <= E[i][0], E[i][1] <= N
Time Limit: 1 sec
Approaches
Here, we will use Prim’s algorithm to calculate MST(Minimum Spanning Tree). The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
Prim’s algorithm is a greedy algorithm that maintains two sets, one represents the vertices included (in MST), and the other represents the vertices not included (in MST). At every step, it finds the minimum weight edge that connects vertices of set 1 to vertices of set 2 and includes the vertex on the other side of edge to set 1(or MST).
Prim’s algorithm finds the minimum weight edge in the cut and includes the vertex on this edge in MST and repeats this process till all the vertices are included in the MST.
- Create an array ‘INCLUDED_MST’, that represents whether or not the current vertex is included (in MST).
- Create another array ‘MIN_EDGE_CUT’, that represents the minimum weight edge in the cut from the current vertex.
- Initialize ‘MIN_EDGE_CUT' as INFINITE for all the vertices and 0 for the first vertex.
- Pick a vertex(say ‘U’) with ‘MIN_EDGE_CUT’ value that is not included (in MST) and include it in MST.
- Update the values of ‘MIN_EDGE_CUT’ for all the adjacent vertices that are not included(in MST) for the picked vertex.
- To update values, for every adjacent vertex ‘V’, if the weight of edge ‘U’ - ‘V’ is less than the current ‘MIN_EDGE_CUT’ value of ‘V’, update the ‘MIN_EDGE_CUT’ value as the weight of the ‘U’ - ‘V’.
- Repeat steps 4, 5, and 6 till all the vertices are not included.
Here, we will use Prim’s algorithm to calculate MST(Minimum Spanning Tree). The idea behind Prim’s algorithm is simple, a spanning tree means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
Prim’s algorithm is a greedy algorithm that maintains two sets, one represents the vertices included (in MST), and the other represents the vertices not included (in MST). At every step, it finds the minimum weight edge that connects vertices of set 1 to vertices of set 2 and includes the vertex on the other side of edge to set 1(or MST).
Prim’s algorithm finds the minimum weight edge in the cut and includes the vertex on this edge in MST and repeats this process till all the vertices are included in the MST.
The first vertex int pair is the minimum weight vertex ,extract it from the priority queue and node name is stored at the second of the pair( it has to be done this way to keep the vertices sorted order with respect weight) weight must be the first item in the pair.
- Create a vector ('WEIGHT[]') for key and initialize as infinite.
- Create a min priority queue ‘PQ’.
- To keep track of vertices which already have been included in mst.
- Insert source as in priority queue and initialize with 0.
- Keep iterating until ‘PQ’ isn’t empty.
- The first vertex int pair is the minimum weight vertex ,extract it from the priority queue and node name is stored at the second of the pair( it has to be done this way to keep the vertices sorted order with respect weight) weight must be the first item in the pair.
- Explore all adjacent popped node and if not visit, relax them.
- Let’s say ‘V’ is an adjacent node that is not in mst and the weight of ('U','V') is smaller than the current weight of ‘V’, insert it into the priority queue.
- Keep iterating until the queue isn’t empty.