Prim's MST

Posted: 17 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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 :

alt text

The MST (Minimum Spanning Tree) for the above graph is:

alt text

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
Approach 1

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.

 

  1. Create an array ‘INCLUDED_MST’, that represents whether or not the current vertex is included (in MST).
  2. Create another array ‘MIN_EDGE_CUT’, that represents the minimum weight edge in the cut from the current vertex.
  3. Initialize ‘MIN_EDGE_CUT' as INFINITE for all the vertices and 0 for the first vertex.
  4. Pick a vertex(say ‘U’) with ‘MIN_EDGE_CUT’ value that is not included (in MST) and include it in MST.
  5. Update the values of ‘MIN_EDGE_CUT’ for all the adjacent vertices that are not included(in MST) for the picked vertex.
  6. 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’.
  7. Repeat steps 4, 5, and 6 till all the vertices are not included.
Try Problem