Finding minimal spanning tree of a graph using Kruskal's algorithm

Question

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?

Answer 1

The first two comments already imparted a negative impression of the code — something you definitely don't want to do in an interview.

# Within code v = vertice, r = root, e = edge, u = union, m = make, f = find.

# Global Variables for simplifying code.

The first comment indicates that your function names are horrible. The second comment indicates that you don't know how to use variables with the correct scope.

---

G = {
    'vertices': [0, 1, 2, 3, 4, 5, 6, 7],
    'edges': set([
        (1, 6, 5),
        (3, 5, 2),
        …,
        (2, 1, 7),
        ])
    }

Specifying the vertices is redundant, right? All of the relevant vertices should already be mentioned as one of the endpoints of an edge. (And if that is not the case, then you have a lone disconnected vertex, and it would be impossible to make a spanning tree. Such is the case, in fact, with vertex 7 in your example.)

Furthermore, your Question3() function returns a graph as a set of edges. It would also make sense that it accepts a graph as a set of edges.

The Question3 function should look more like this:

def kruskal_mst(graph_edges):
    vertex_parents = {
        v: v for v in itertools.chain(*[(v1, v2) for v1, v2, w in edges])
    }
    vertex_ranks = {v: 0 for v in vertex_parents}

    mst = set()
    for e in edges:
        v1, v2, weight = e
        if find(v1, vertex_parents) != find(v2, vertex_parents):
            union(v1, v2, vertex_parents, vertex_ranks)
            mst.add(e)
    return mst

print kruskal_mst([
    (1, 6, 5),
    (3, 5, 2),
    (5, 4, 9),
    …,
    (2, 1, 7)
])

---

Your code ignores edge weights completely. (Note that your solution uses the (2, 4, 9) edge rather than the lower-cost (4, 2, 3) edge. Also, to connect vertex 3 into the MST, it uses the (2, 3, 6) edge rather than (3, 5, 2).)