Kruskal

In this assignment, you will implement Kruskal$$s Algorithm. There are very few rules in how you approach your implementation.

You must only use the standard libraries or implement yourself.

You may use code from previous assignments.

You must follow the general algorithm concepts as described in lecture$/$lecture notes$/$textbook$.$

You must sort an array of edges using Quick Sort. You may modify your sort code from previous homeworks, but you need to write the sort for edges yourself.

When printing edges, you are required to print the smaller node first. For example, if there is an edges from $1$ to $7$ always print it as $(1,7)$ never $(7,1).$ This is a necessity for the autograder.

Since you need to compare edges, you need to break ties. To compare two edges:

The lower weight wins

On tied weight the smaller from node wins

On tied from node the smaller to node wins

You will implement a program that ask for one input. The only input is the name of a file containing the graph. You will run Kruskal$$s Algorithm on this graph. You will print out the edges as they are added to the MST$.$ Then you will print the total weight of the MST$.$

You may assume that you will always be given valid filename. You do not need to do error checking.

You may also assume that all edge weights will be positive non$-$zero integers.

File Format

The first line of the file is an integer containing the number of nodes in the graph.

Every other line contains three numbers seperated by spaces. The first number is the from edge. The second number is the to edge. The third number is the weight.

This is an undirected graph. Each edge listed in the file may be taken either direction.

Graphs

You are provided with three graphs as example input. They are in the folder graphs. There is also a folder img. It contains images of the graphs. These may be helpful for debugging. The code you write will not use the images at all, they are just provided for reference.

Readme

If there is anything you want to grader to know when reviewing your assignment please put it in readme.md$.$

Examples

Example Graph $01$

Enter File Containing Graph:

submission$/$files$/$graphs$/$graph$01.$txt

Running Kruskal's Algorithm

Input File: submission$/$files$/$graphs$/$graph$01.$txt

Added Edge: $(0,2)$ with weight $1$

Added Edge: $(3,5)$ with weight $2$

Added Edge: $(1,4)$ with weight $3$

Added Edge: $(2,5)$ with weight $4$

Added Edge: $(1,2)$ with weight $7$

MST Weight: $17$

Example Graph $02$

Enter File Containing Graph:

submission$/$files$/$graphs$/$graph$02.$txt

Running Kruskal's Algorithm

Input File: submission$/$files$/$graphs$/$graph$02.$txt

Added Edge: $(6,7)$ with weight $1$

Added Edge: $(5,6)$ with weight $2$

Added Edge: $(2,8)$ with weight $3$

Added Edge: $(0,1)$ with weight $4$

Added Edge: $(2,5)$ with weight $5$

Added Edge: $(2,3)$ with weight $7$

Added Edge: $(1,2)$ with weight $8$

Added Edge: $(3,4)$ with weight $11$

MST Weight: $41$

Example Graph $03$

Enter File Containing Graph:

submission$/$files$/$graphs$/$graph$03.$txt

Running Kruskal's Algorithm

Input File: submission$/$files$/$graphs$/$graph$03.$txt

Added Edge: $(0,7)$ with weight $16$

Added Edge: $(2,3)$ with weight $17$

Added Edge: $(1,7)$ with weight $19$

Added Edge: $(0,2)$ with weight $26$

Added Edge: $(5,7)$ with weight $28$

Added Edge: $(4,5)$ with weight $35$

Added Edge: $(2,6)$ with weight $40$

MST Weight: $181$

Rubric

All points can be earned by the autograder. If you fail the autograder, a manual review will be completed on the assignment.

Manual Deductions will be applied for break either of the following rules:

$-40$ points for using any library not in the C standard

$-50$ points for solving the problem without using a custom Quick Sort

The test file names tell you what they test. The file test$\_$G$1.$txt tests Graph $1.$

Component Points

test$\_$G$1.$txt $33$

test$\_$G$2.$txt $33$

test$\_$G$3.$txt $34$