You will implement two algorithms to find the shortest path in a graph.

def prim(G,start_node): Takes a graph G and node to start at. Prims edges used in MST.

def kruskal(G): Takes a graph G and prints the edges in the MST in order found.

You may represent the graphs as adjacency matrix or list. You MAY NOT include any graph libraries.

The graph you are working on will be give in a file with the following format. The graph is undirected. That means if an edge from 2 to 1 is in the file, it may be used in both directions.

Line 1: The number of Nodes in the Graph

Lines 2-EOF: Every other line in the file contains an edge

First Value is the first node

Second Value is the second node

Third Value is the weight of the edge

Note: You should store the weights as floats.

The program will have a text interface. First ask for the file name of the graph to work with. Then implement 4 text commands.

prim x - Runs Pim's Algorithm starting at node X. X must be an integer

kruskal - Runs Kruskal's algorithm

help - prints this list of commands

exit - Exits the program

On a bad command print out "Unknown Command"

You must implement this using only standard python3 libraries. You may not use any outside libraries. For example, open source graph libraries.

When printing an edge, always print the smaller vertex first then the larger vertex. This will give a consistent pattern for ZyBooks.

Example Execution Traces are provided below.

Welcome to Minimum Spanning Tree Finder Give the file name graph is in: input1.txt Commands: exit or ctrl-d - quits the program help - prints this menu prim integer_value - run's Prim's algorithm starting at node given kruskal - runs Kruskal's algorithm Enter command: kruskal Running Kruskal's Algorithm Select Edge: [0, 2, 1.0] Select Edge: [3, 5, 2.0] Select Edge: [1, 4, 3.0] Select Edge: [2, 5, 4.0] Select Edge: [1, 2, 7.0] Enter command: exit Bye

----------

Welcome to Minimum Spanning Tree Finder Give the file name graph is in: input1.txt Commands: exit or ctrl-d - quits the program help - prints this menu prim integer_value - run's Prim's algorithm starting at node given kruskal - runs Kruskal's algorithm Enter command: Bad Command Unknown Command Enter command: help Commands: exit or ctrl-d - quits the program help - prints this menu prim integer_value - run's Prim's algorithm starting at node given kruskal - runs Kruskal's algorithm Enter command: prim 0 Running Prim's Algorithm Starting Node: 0 Added 2 Using Edge [0, 2, 1.0] Added 5 Using Edge [2, 5, 4.0] Added 3 Using Edge [3, 5, 2.0] Added 1 Using Edge [1, 2, 7.0] Added 4 Using Edge [1, 4, 3.0] Enter command: exit Bye

----------

The content of the files is shown below.

input1.txt

6 0 3 5 3 5 2 5 4 10 4 1 3 1 0 8 0 2 1 2 3 6 2 5 4 2 4 9 2 1 7 input2.txt

9 0 1 4 0 7 10 1 7 13 7 8 9 7 6 1 1 2 8 8 2 3 8 6 6 2 3 7 2 5 5 6 5 2 3 5 14 3 4 11 5 4 12 input3.txt

8 4 5 35 4 7 37 5 7 28 0 7 16 1 5 32 0 4 38 2 3 17 1 7 19 0 2 26 1 2 36 1 3 29 2 7 34 6 2 40 3 6 52 6 0 58 6 4 93