Description
In this assignment, 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.
