Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- parent = dict()
- rank = dict()
- def make_set(vertice):
- parent[vertice] = vertice
- rank[vertice] = 0
- def find(vertice):
- if parent[vertice] != vertice:
- parent[vertice] = find(parent[vertice])
- print (vertice)
- return parent[vertice]
- def union(vertice1, vertice2):
- root1 = find(vertice1)
- root2 = find(vertice2)
- if root1 != root2:
- if rank[root1] > rank[root2]:
- parent[root2] = root1
- else:
- parent[root1] = root2
- if rank[root1] == rank[root2]: rank[root2] += 1
- def kruskal(graph):
- for vertice in graph['vertices']:
- make_set(vertice)
- minimum_spanning_tree = set()
- edges = list(graph['edges'])
- edges.sort()
- for edge in edges:
- weight, vertice1, vertice2 = edge
- if find(vertice1) != find(vertice2):
- union(vertice1, vertice2)
- minimum_spanning_tree.add(edge)
- return minimum_spanning_tree
- graph = {
- 'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
- 'edges': set([
- (1, 'A', 'B'),
- (3, 'B', 'C'),
- (5, 'C', 'D'),
- (1, 'A', 'D'),
- (3, 'E', 'D'),
- (4, 'B', 'E'),
- ])
- }
- print (kruskal(graph))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement