, you need to implement the Prim’s algorithm in O(ElogV) and Kruskal’s algorithm in O(ElogE) to find the Minimum Spanning Tree (MST) of a given connected weighted undirected graph.
Input/Output:
You will take input from an input file and print output to an output file. Keep provision of printing output to the console as well (but printing both to file and to console simultaneously will not be necessary).
Input Format:
The first line of input will have two space-separated non-negative integers N and M, the number of nodes and edges in the graph.
In the next M lines, there will be three space-separated integers, u, v, w denoting an edge where u and v denote the endpoints and w denotes the weight of the bidirectional edge. (0 ≤ u, v < N)
Output Format:
Print the total weight of the MST of the given graph in the first line. In the following lines, you need to print the MST (printing N-1 edges will be sufficient). For Prim’s algorithm, you need to mention, which node was used as the root. If there are multiple MSTs, finding and printing any one of them will be sufficient.
See the sample I/O for further clarification.
Special Instructions:
Write readable, re-usable, well-structured, quality code. This includes but is not limited to writing appropriate functions for implementation of the required algorithms, meaningful naming of the variables, suitable comments where required, proper indentation etc. You will need to use your offline implementation to solve the onlines.
Please DO NOT COPY solutions from anywhere (your friends, seniors, internet etc.). Any form of plagiarism (irrespective of source or destination), will result in getting -100% marks in the offline. Also, be informed that for repeated offence of plagiarism, the departmental policies suggest stricter measures.
Page 1 of 2
Sample I/O:
Input
Output
7 11
0 1 10
0 2 20
1 2 10 1 3 5
1 4 10
2 5 5
3 4 2
3 6 5
4 5 2
4 6 5
5 6 10
29
Kruskal’s algorithm:
3 4
4 5
1 3
2 5
3 6
0 1
Prim’s Algorithm:
Root node = 3
3 4
4 5
2 5
3 1
3 6
1 0
