CS211-Assignment 7 Kruskal’s algorithm to Find MST Solved

The objective of this assignment is to implement Kruskal’s algorithm to find a minimum spanning tree (MST) of the given connected edge-weighted undirected graph.

 

Inputs
 

Your program should accept an input file as command-line argument. A typical execution of your program will be ‘./a.out sample.graph’.

 

The input file represents a connected undirected graph with integer weights on edges. Every node (vertex) in the graph is labelled uniquely with a non-negative integer. Every line in the input file is of the form ​x y w​, which represents an edge between node x​ and node y​ ​, where the weight of the edge is ​w​. No edge is repeated in the input file. Since edge-weights are unique and you are using Kruskal’s algorithm, it is guaranteed that the output is unique.

 

Task
 

Implement Kruskal’s algorithm to find a minimum spanning tree of the given connected, weighted, and undirected graph. It is recommended that you use disjoint-set forest data structure with union-by-rank and path-compression heuristics. But a simpler implementation of the algorithm will also be accepted with full credits.

 

Output
 

Your program should create a file named ‘mst.txt’. Every line in the output file should be of the form ​x y w​, which represents an edge ​xy with weight ​w in the minimum spanning tree. The edges should be present in the file in the non-decreasing order of their weights.