Description: You are to implement Kruskal's Algorithm and Prim’s Algorithm for finding Minimum Spanning Trees (MSTs) of undirected positively weighted graphs adhering to the specifications detailed below.
I/O Specifications: You will read your input graph from an input file named graphin.txt of the following adjacency list representation where each xij is the j'th neighbor of vertex i (vertex labels are 1 through n) and wij is the weight of the edge between vertices i and Xij:
Your output from Kruskal’s algorithm will be to a file named kruskalout.txt, and your output from Prim’s algorithms will be to primout.txt, both of the following edge list form:
x1 y1 x2 y2
.
. xn-1 yn-1
This is just a list of the n-1 edges involved in the computed MST in the order of computation.
Algorithmic specifications:
Your algorithm must run in O(E log V) time on any input graph. Therefore, you must use the adjacency list representation for input processing. E.g., you may implement your adjacency list as an array of linked lists or an array of vectors. For Kruskal's algorithm, you must sort the edges by weight using an efficient (O(m log m)) sorting algorithm that you already implemented. In growing your forest of trees, you must implement an efficient Disjoint Set structure in which both the union operation and the find operation take O(log n) time, using either union-by-size or union-by-depth heuristics, stated in comments. For Prim’s algorithms, you have already partially implemented a Heap and need to complete the implementation for a min-Heap including heap insertion, decrease key, and deletion, being careful to be able to access the heap positions from the adjacency list and vice versa.
