I

In this assignment you are to write a Python program to create a minimum spanning tree $($MST$)$ of a graph using Kruskal's algorithm.

You are provided with the template in which you must:

$(1)$ implement code to print an adjacency list of a graph;

$(2)$ implement a function to construct a minimum spanning tree $($MST$)$ of a given graph using Kruskal's algorithm.

Your program must:

take a file containing graph vertices, edges, and weights as a command line argument,

insert vertices, edges, and weights into the graph,

print adjacency list representation of a graph $(1),$ and

print minimum spanning tree $($MST$)$ of the graph $(2).$

Following is the output of the program run applied on provided test file:EdgeWeight$(0,5)2(5,2)1(0,4)1(5,3)3(1,2)4$

Together with your source code include a separate file

Namingformat.py with your information as the values of the following variables:You must properly cite the sources if you use any help from peers or any code$/$ideas from online resources. Failure to do so will be treated as a plagiarism. Properly citing the sources should be done as a comment in your code. Some examples:

mport sysclass Graph: def $\_\_$init$\_\_($self$)$: self.verList $=\{\}$ self.numVertices $=0$ class $\_\_$Vertex: def $\_\_$init$\_\_($self$,$ key$)$: self.id $=$ key self.connectedTo $=\{\}$ def getId$($self$)$: return self.id def getConnections$($self$)$: return self.connectedTo.keys$()$ def getWeight$($self$,$ nbr$)$: return self.connectedTo$[$nbr$]$ def addNeighbor$($self$,$ nbr$,$ weight $=0)$: self.connectedTo$[$nbr$]=$ weight def $\_\_$str$\_\_($self$)$: return f$"$connected to: $\{$str$([$x$.$id for x in self.connectedTo$])\}"$ def addVertex$($self$,$ key$)$: self.numVertices $+=1$ newVertex $=$ Graph.$\_\_$Vertex$($key$)$ self.verList$[$key$]=$ newVertex return newVertex def getVertex$($self$,$ n$)$: if n in self.verList: return self.verList$[$n$]$ else: return None def $\_\_$contains$\_\_($self$,$ n$)$: return n in self.verList def addEdge$($self$,$ source, destination, weight $=0)$: if source not in self.verList: newVertex $=$ self.addVertex$($source$)$ if destination not in self.verList: newVertex $=$ self.addVertex$($destination$)$ self.verList$[$source$].$addNeighbor$($self$.$verList$[$destination$],$ weight$)$ def getVertices$($self$)$: return self.verList.keys$()$ def $\_\_$iter$\_\_($self$)$: return iter$($self$.$verList.values$())$ def dfs$($self$,$ s$,$ visited $=$ None$)$: if visited is None: visited $=$ set$()$ if s not in visited: print$($s$,$ end $="")$ visited.add$($s$)$ for next$\_$node in $[$x$.$id for x in self.verList$[$s$].$connectedTo$]$: self.dfs$($next$\_$node, visited$)$ def bfs$($self$,$ s$,$ visited $=$ None$)$: if visited is None: visited $=$ set$()$ q $=$ Queue$()$ q$.$put$($s$)$ visited.add$($s$)$ while not q$.$empty$()$: current$\_$node $=$ q$.$get$()$ print$($current$\_$node, end $="")$ for next$\_$node in $[$x$.$id for x in self.verList$[$current$\_$node$].$connectedTo$]$: if next$\_$node not in visited: q$.$put$($next$\_$node$)$ visited.add$($next$\_$node$)$ def kruskals$($self$)$: vertices$\_$sets $=$ set$()$ edges$\_$dict $=$ dict$()$ MST $=$ set$()$ ### WRITE YOUR CODE HERE ### return MSTdef main$()$: # create an empty graph graph $=$ Graph$()$ # get graph vertices & edges from input file and add them to the graph file $=$ open$($sys$.$argv$[1],"$r$")$ for line in file: values $=$ line.split$()$ graph.addEdge$($int$($values$[0]),$ int$($values$[1]),$ int$($values$[2]))$ graph.addEdge$($int$($values$[1]),$ int$($values$[0]),$ int$($values$[2]))$ # print adjacency list representation of the graph print$()$ ### WRITE YOUR CODE HERE ### # create graph MST MST $=$ graph.kruskals$()$ # print graph MST print$()$ print$("$Graph MST:$")$ print$("$Edge$\backslash$t$\backslash$tWeight$")$ for edge in MST: print$($f$"\{$edge$[0]\}\backslash$t$\backslash$t$\{$edge$[1]\}")$main$()$