Python This assignment uses two different algorithms to find Minimum Spanning Trees.

File 1: main.py

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 command line 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 menu

exit or ctrl-D - Exits the program

You must implement this using only standard python3 libraries.