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.
