#### Minimum Spanning Tree Boruvka

```class Graph:
"""
Data structure to store graphs (based on adjacency lists)
"""

def __init__(self):

self.num_vertices = 0
self.num_edges = 0

"""
Adds a vertex to the graph

"""
self.num_vertices += 1

"""
Adds an edge to the graph

"""

return

def distinct_weight(self):
"""
For Boruvks's algorithm the weights should be distinct
Converts the weights to be distinct

"""
edges = self.get_edges()
for edge in edges:
for i in range(len(edges)):
edges[i] = list(edges[i])

edges.sort(key=lambda e: e)
for i in range(len(edges) - 1):
if edges[i] >= edges[i + 1]:
edges[i + 1] = edges[i] + 1
for edge in edges:

def __str__(self):
"""
Returns string representation of the graph
"""
string = ""
string += "%d -> %d == %d\n" % (head, tail, weight)
return string.rstrip("\n")

def get_edges(self):
"""
Returna all edges in the graph
"""
output = []
return output

def get_vertices(self):
"""
Returns all vertices in the graph
"""

@staticmethod
def build(vertices=None, edges=None):
"""
Builds a graph from the given set of vertices and edges

"""
g = Graph()
if vertices is None:
vertices = []
if edges is None:
edge = []
for vertex in vertices:
for edge in edges:
return g

class UnionFind:
"""
Disjoint set Union and Find for Boruvka's algorithm
"""

def __init__(self):
self.parent = {}
self.rank = {}

def __len__(self):
return len(self.parent)

def make_set(self, item):
if item in self.parent:
return self.find(item)

self.parent[item] = item
self.rank[item] = 0
return item

def find(self, item):
if item not in self.parent:
return self.make_set(item)
if item != self.parent[item]:
self.parent[item] = self.find(self.parent[item])
return self.parent[item]

def union(self, item1, item2):
root1 = self.find(item1)
root2 = self.find(item2)

if root1 == root2:
return root1

if self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
return root1

if self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
return root2

if self.rank[root1] == self.rank[root2]:
self.rank[root1] += 1
self.parent[root2] = root1
return root1

@staticmethod
def boruvka_mst(graph):
"""
Implementation of Boruvka's algorithm
>>> g = Graph()
>>> g = Graph.build([0, 1, 2, 3], [[0, 1, 1], [0, 2, 1],[2, 3, 1]])
>>> g.distinct_weight()
>>> bg = Graph.boruvka_mst(g)
>>> print(bg)
1 -> 0 == 1
2 -> 0 == 2
0 -> 1 == 1
0 -> 2 == 2
3 -> 2 == 3
2 -> 3 == 3
"""
num_components = graph.num_vertices

union_find = Graph.UnionFind()
mst_edges = []
while num_components > 1:
cheap_edge = {}
for vertex in graph.get_vertices():
cheap_edge[vertex] = -1

edges = graph.get_edges()
for edge in edges:
for edge in edges:
set2 = union_find.find(tail)
if set1 != set2:
if cheap_edge[set1] == -1 or cheap_edge[set1] > weight:

if cheap_edge[set2] == -1 or cheap_edge[set2] > weight:
for vertex in cheap_edge:
if cheap_edge[vertex] != -1:  