In this problem you will need to implement Kruskal’s algorithmto find the minimal spanning tree of a graph. When you finish yourimplementation you will need to run in on an input graph I amgiving to you in file “ “graph_example.py”. I am giving you for this homework two files : 1-“graph_example.py” has a graph example using networkx. Thiswill get you started using the networkx library. We do not needmuch beyond knowing how to create a graph, how to add a node andedge to that graph. In this file I am loading a graph example thatcomes with the package and then list its nodes and edges. I thenassigned a weight to the edges of that graph. If you run that fileyou will see that it prints to you the list of nodes, list of edgesand their weights. 2- The second file “unionfind.py” is a simple implementation forunion-find data structure. You will need this file in order toeasily implement the Kruskal’s algorithm graph_example.py import networkx as nx

from unionfind import *

# Load a graph example from networkx graph=nx.house_x_graph() print(“The nodes of the graph are given by the list : “) print(graph.nodes()) print(“The edges of the graph are given by the list : “) print(graph.edges()) # here we are giving weights to the edges

initweight=1

for edge in graph.edges():

graph.add_edge(edge[0], edge[1], weight=initweight)

initweight=initweight+1 # check the weights of the edges:

  

for edge in graph.edges():

a=edge[0]

b=edge[1]

print(“edge “+str(edge)+” has weight ” + str(graph[a][b][‘weight’])) # now you will need to calculate the minimal spanning tree for thegraph above. # Implement Kruskal algorothm and run it on the above graphexample and record your result.   unionfind.py class UnionFind:

def __init__(self):

”’

Create an empty union find data structure.”’

self.num_weights = {}

self.parent_pointers = {}

self.num_to_objects = {}

self.objects_to_num = {}

self.__repr__ = self.__str__

def insert_objects(self, objects):

”’

Insert a sequence of objects into the structure. All must be Pythonhashable.”’

for object in objects:

self.find(object);

def find(self, object):

”’

Find the root of the set that an object is in.

If the object was not known, will make it known, and it becomes itsown set.

Object must be Python hashable.”’

if not object in self.objects_to_num:

obj_num = len(self.objects_to_num)

self.num_weights[obj_num] = 1

self.objects_to_num[object] = obj_num

self.num_to_objects[obj_num] = object

self.parent_pointers[obj_num] = obj_num

return object

stk = [self.objects_to_num[object]]

par = self.parent_pointers[stk[-1]]

while par != stk[-1]:

stk.append(par)

par = self.parent_pointers[par]

for i in stk:

self.parent_pointers[i] = par

return self.num_to_objects[par]

def union(self, object1, object2):

”’

Combine the sets that contain the two objects given.

Both objects must be Python hashable.

If either or both objects are unknown, will make them known, andcombine them.”’

o1p = self.find(object1)

o2p = self.find(object2)

if o1p != o2p:

on1 = self.objects_to_num[o1p]

on2 = self.objects_to_num[o2p]

w1 = self.num_weights[on1]

w2 = self.num_weights[on2]

if w1

o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1

self.num_weights[on1] = w1+w2

del self.num_weights[on2]

self.parent_pointers[on2] = on1 kruskalsalgorithm.py from unionfind import *

import networkx as nx class kruskalsalgorithm():

def __init__(self,inputgraph):

self.original_graph=inputgraph

self.tree=nx.Graph() # uncomment the following function and start your implementation asdescribed in lecture 2

def spanningtree(self): . . .