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:
1: x11 w11 x12 w12 x13 w13... 2: x21 w21 x22 w22 x23 x23 ...
.
. n: xn1 wn1 xn2 wn2 xn3 wn3 ...
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.
This project has no report. However, you must document amply and appropriately.
What to Turn in: You must turn in a single zipped file containing your source code, a Makefile if needed, I/O files, and a README file indicating how to execute your program (especially if not written in C++ or Java). If your program cannot be compiled and/or run on home.cs.siue.edu, you must show me your code running in office hours.
This assignment is due by MIDNIGHT on Monday, March 13th. Late submissions carry a -20 % per day late penalty.
