I am doing some practice interview questions for class, one of the questions is:
Given an undirected graph G, find the minimum spanning tree. Function should take in and output an adjacency list.
Here is the code that I have which works using Kruskal's algorithm:
### Question 3 main function and helper functions.
# Within code v = vertice, r = root, e = edge, u = union, m = make, f = find.
# Global Variables for simplifying code.
parent = dict()
rank = dict()
# Find vertices.
def f(v):
if parent[v] != v:
parent[v] = f(parent[v])
return parent[v]
# Make vertices.
def m(v):
parent[v] = v
rank[v] = 0
# Creates union between vertices.
def u(v1, v2):
r1 = f(v1)
r2 = f(v2)
if r1 != r2:
if rank[r1] > rank[r2]:
parent[r2] = r1
else:
parent[r1] = r2
if rank[r1] == rank[r2]: rank[r2] += 1
# Main Function.
def Question3(G):
for v in G['vertices']:
m(v)
edges = list(G['edges'])
MST = set()
for e in edges:
v1, v2, weight = e
if f(v1) != f(v2):
u(v1, v2)
MST.add(e)
return MST
G = {
'vertices': [0, 1, 2, 3, 4, 5, 6, 7],
'edges': set([
(1, 6, 5),
(3, 5, 2),
(5, 4, 9),
(4, 2, 3),
(1, 1, 8),
(0, 2, 1),
(2, 3, 6),
(2, 5, 4),
(2, 4, 9),
(2, 1, 7),
])
}
print "Minimum Spanning Tree of G:"
print Question3(G)
# Expected Output.
# Minimum Spanning Tree of G:
# set([(1, 6, 5), (2, 4, 9), (2, 5, 4), (2, 1, 7), (2, 3, 6), (0, 2, 1)])
print """---End Question 3---
"""
Are there any unnecessary bits of code in my solution and/or is there a more efficient way I could be going about this problem?