DFS vs. Kruskal runtime (maze generation)

Question

I have written two algorithms for creating unique mazes, one of them using depth-first-search (DFS) and the other using Kruskal's. The DFS algorithm performs as expected, however Kruskal's algorithm runs marginally slower than DFS and I do not know why.

I had written Kruskal's algorithm in Python.

I suspect the random.choice() function seems to be the underlying problem. The difference in runtime becomes noticeable when (r, c) > 30.

Here is the code for Kruskal's algorithm:

# Create a list of all possible edges
def create_edges(r, c):
    edges = []

    for y in range(r):
        for x in range(c):
            i = (y, x)

            for d in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                p = tuple(map(sum, zip(d, i)))

                py = p[0]
                px = p[1]

                if px in range(c) and py in range(r):
                    edges.append([i, p])

return edges

def kruskal(r, c, sz):
    path = []

    # Create a list of parent root nodes
    roots = {(y, x) : [(y, x)] for y in range(r) for x in range(c)}

    edges = create_edges(r, c)

    while edges:
        # Choose a random edge
        edge = random.choice(edges) 

        parent = edge[0]
        child  = edge[1]

        parent_set = get_set(roots, parent)
        child_set  = get_set(roots,  child)

        # Check if the parent / child are already in the same set
        if parent_set == child_set:
            rev_edge = edge.reverse()

            if rev_edge in edges:
                edges.remove(rev_edge)

            edges.remove(edge)

            continue

        roots[parent_set] += roots[child_set]
        roots.pop(child_set)

        path.extend((parent, child))

        rev_edge = edge.reverse()

        if rev_edge in edges:
            edges.remove(rev_edge)

        edges.remove(edge)

    return path

def get_set(roots, member):
    s = None

    for parent, children in roots.items():
        if member in children:
            s = parent

    return s

def create_maze(t, r, c, sz):
    maze = [['|_' for _ in range(c)] for _ in range(r)]

    for cell in maze: cell.append('| ')

    wd = {'DOWN' : ( 1,  0),
          'UP'   : (-1,  0),
          'LEFT' : ( 0, -1),
          'RIGHT': ( 0,  1)}

    for n in range(len(t) - 1):
        a = n
        b = n + 1

        p1 = t[a]
        p2 = t[b]

        ay, ax = p1[0], p1[1]
        by, bx = p2[0], p2[1]

        w = tuple(numpy.array(p2) - numpy.array(p1))

        if w in wd.values():

            k = list(wd.keys())[list(wd.values()).index(w)]

            if k ==  'DOWN': maze[ay][ax] = maze[ay][ax].replace('_', ' ')
            if k ==    'UP': maze[by][bx] = maze[by][bx].replace('_', ' ')
            if k ==  'LEFT': maze[ay][ax] = maze[ay][ax].replace('|', ' ')
            if k == 'RIGHT': maze[by][bx] = maze[by][bx].replace('|', ' ')

    return maze

def print_maze(maze, r, c, delay = 0):
    s, l = min((r, c)), max((r, c))

    a = 1 / (4 * r * c)
    e = (1 / (s * l)) ** 2

    delay = (a * 2.718 ** (-1 * e)) ** 0.5

    time.sleep(delay)

    print(' _' * c)

    for iy in range(r):
        for ix in range(c + 1):
            print(maze[iy][ix], end = '')

        print('')

    print('')

def main():
    r = 30
    c = 30

    sz = r * c

    path = kruskal(r, c, sz)

    maze = create_maze(path, r, c, sz)

    print_maze(maze, r, c)

if __name__ == "__main__":
    main()