迷宫生成：Kruskal算法较DFS运行缓慢的原因排查

我实现了两种生成唯一迷宫的算法：深度优先搜索（DFS）和Kruskal算法。DFS运行符合预期，但Kruskal算法的速度明显慢于DFS，当迷宫尺寸(r,c)＞30时，两者的运行时长差异会变得非常明显。我怀疑random.choice函数是性能瓶颈，但不确定具体原因。

原Kruskal算法代码 #

import random
import numpy as np
import time

# 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.copy()
            rev_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.copy()
        rev_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(np.array(p2) - np.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()

性能瓶颈分析 #

你的代码性能问题核心并非random.choice，而是以下几个关键低效点：

1. get_set函数的线性遍历：每次查找节点所属集合时，需要遍历整个roots字典，且member in children是列表的O(n)操作。随着迷宫规模扩大，集合合并后列表长度增加，这个操作的时间复杂度会急剧上升，是最大的性能瓶颈。
2. 边列表的remove操作：edges.remove(edge)和rev_edge in edges都是O(n)操作，每次删除元素都要遍历整个列表，随着边数量减少，该操作的开销依然不可忽视。
3. 重复生成反向边：create_edges会生成双向边（比如(i,p)和(p,i)），后续需要额外检查并删除反向边，增加了不必要的计算。

优化方案 #

1. 使用并查集（Union-Find）结构：替换当前的roots字典，实现路径压缩和按秩合并，将查找和合并操作的时间复杂度降至近似O(1)。
2. 预处理边列表：生成边时只保留单向边（比如仅向右、向下的边），避免后续处理反向边的开销；提前打乱边列表，顺序遍历即可代替每次random.choice。
3. 避免列表的remove操作：通过遍历打乱后的边列表，跳过已处理的边，或者用集合存储边（但集合中不可变元素更高效，所以将边转为元组）。

优化后的代码 #

import random
import numpy as np
import time

# 生成单向边（仅向右、向下，避免重复）
def create_edges(r, c):
    edges = []
    for y in range(r):
        for x in range(c):
            # 向右的边
            if x + 1 < c:
                edges.append(((y, x), (y, x+1)))
            # 向下的边
            if y + 1 < r:
                edges.append(((y, x), (y+1, x)))
    return edges

# 并查集实现
class UnionFind:
    def __init__(self, r, c):
        self.parent = {(y, x): (y, x) for y in range(r) for x in range(c)}
        self.rank = {(y, x): 0 for y in range(r) for x in range(c)}
    
    def find(self, node):
        # 路径压缩
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]
    
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        if root1 == root2:
            return False  # 已在同一集合
        # 按秩合并
        if self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        else:
            self.parent[root2] = root1
            if self.rank[root1] == self.rank[root2]:
                self.rank[root1] += 1
        return True

def kruskal(r, c, sz):
    path = []
    uf = UnionFind(r, c)
    edges = create_edges(r, c)
    random.shuffle(edges)  # 提前打乱边列表
    
    for edge in edges:
        node1, node2 = edge
        if uf.union(node1, node2):
            path.extend((node1, node2))
    
    return path

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):
        p1 = t[n]
        p2 = t[n+1]
        dy, dx = p2[0] - p1[0], p2[1] - p1[1]
        direction = (dy, dx)
        
        if direction == wd['DOWN']:
            maze[p1[0]][p1[1]] = maze[p1[0]][p1[1]].replace('_', ' ')
        elif direction == wd['UP']:
            maze[p2[0]][p2[1]] = maze[p2[0]][p2[1]].replace('_', ' ')
        elif direction == wd['LEFT']:
            maze[p1[0]][p1[1]] = maze[p1[0]][p1[1]].replace('|', ' ')
        elif direction == wd['RIGHT']:
            maze[p2[0]][p2[1]] = maze[p2[0]][p2[1]].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 row in maze:
        print(''.join(row))
    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()

优化效果说明 #

• 并查集的路径压缩和按秩合并将集合查找/合并操作从O(n)降至近似O(1)，这是性能提升的核心。
• 单向边生成避免了反向边的重复处理，减少了一半的边数量。
• 提前打乱边列表代替每次random.choice，避免了列表删除的O(n)开销。

内容的提问来源于stack exchange，提问作者DuckyShine