CSE208 Assignment- Minimum Spanning Tree Solved

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.

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

Submission Guideline:

1. Create a directory with your 7 digit student id as its name
2. Put the source files only into the directory created in step 1
3. Zip the directory (compress in .zip format; .rar, .7z or any other format is not acceptable)
4. Upload the .zip file on moodle.

For example, if your student id is 1705xxx, create a directory named 1705xxx. Put only your source files (.c, .cpp, .java, .h, etc.) into 1705xxx. Compress 1705xxx into 1705xxx.zip and upload the 1705xxx.zip on moodle.

Sample I/O: Input

7 11
0 1 10 0 2 20 1 2 10 135 1 4 10 255 342 365 452 465 5 6 10

Output

29
Kruskal’s algorithm: 34
45
13
25
36
01
Prim’s Algorithm: Root node = 3
34
45
25
31
36
10