![\"python\u5982\u4f55\u751f\u6210\u968f\u673a\u8ff7\u5bab\"](\"https:\/\/cdn-kb.worktile.com\/kb\/wp-content\/uploads\/2024\/04\/25104028\/e01a7787-2d20-4b59-9e7d-d7b67d994047.webp\")
<\/p>\n<\/p>\n
\u751f\u6210\u968f\u673a\u8ff7\u5bab\u7684\u5e38\u7528\u65b9\u6cd5\u6709\uff1a\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5\u3001Prim\u7b97\u6cd5\u3001Kruskal\u7b97\u6cd5\u3002<\/strong> \u5176\u4e2d\uff0c\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5\u662f\u4e00\u79cd\u7b80\u5355\u4f46\u6709\u6548\u7684\u751f\u6210\u8ff7\u5bab\u7684\u65b9\u6cd5\uff0c\u5b83\u901a\u8fc7\u9012\u5f52\u5730\u63a2\u6d4b\u8def\u5f84\uff0c\u521b\u5efa\u51fa\u590d\u6742\u4e14\u591a\u53d8\u7684\u8ff7\u5bab\u7ed3\u6784\u3002\u8ba9\u6211\u4eec\u8be6\u7ec6\u63a2\u8ba8\u8fd9\u79cd\u65b9\u6cd5\u3002<\/p>\n<\/p>\n \u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5\u751f\u6210\u8ff7\u5bab\u7684\u6838\u5fc3\u601d\u60f3\u662f\u5229\u7528\u6808\u7684\u7279\u6027\u6765\u8bb0\u5f55\u8def\u5f84\uff0c\u786e\u4fdd\u6bcf\u4e2a\u4f4d\u7f6e\u53ea\u8bbf\u95ee\u4e00\u6b21\u3002\u5177\u4f53\u6b65\u9aa4\u5982\u4e0b\uff1a\u9996\u5148\u9009\u62e9\u4e00\u4e2a\u8d77\u59cb\u70b9\uff0c\u5c06\u5176\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\uff0c\u7136\u540e\u968f\u673a\u9009\u62e9\u4e00\u4e2a\u672a\u8bbf\u95ee\u7684\u76f8\u90bb\u70b9\uff0c\u5c06\u5176\u52a0\u5165\u6808\u4e2d\uff0c\u5e76\u6253\u901a\u4e24\u70b9\u4e4b\u95f4\u7684\u5899\u58c1\u3002\u63a5\u7740\uff0c\u5c06\u65b0\u70b9\u6807\u8bb0\u4e3a\u5df2\u8bbf\u95ee\uff0c\u91cd\u590d\u8fd9\u4e00\u8fc7\u7a0b\uff0c\u76f4\u5230\u6240\u6709\u70b9\u90fd\u88ab\u8bbf\u95ee\u4e3a\u6b62\u3002\u4e3a\u4e86\u9632\u6b62\u8ff7\u5bab\u8fc7\u4e8e\u7b80\u5355\u6216\u65e0\u8da3\uff0c\u53ef\u4ee5\u5728\u4e0d\u540c\u7684\u65b9\u5411\u4e0a\u6dfb\u52a0\u4e00\u5b9a\u7684\u968f\u673a\u6027\uff0c\u4ee5\u589e\u52a0\u8def\u5f84\u7684\u591a\u6837\u6027\u548c\u590d\u6742\u7a0b\u5ea6\u3002<\/p>\n<\/p>\n \u4ee5\u4e0b\u662f\u8be6\u7ec6\u7684\u5185\u5bb9\uff1a<\/p>\n<\/p>\n \u6df1\u5ea6\u4f18\u5148\u641c\u7d22\uff08DFS\uff09\u662f\u4e00\u79cd\u7ecf\u5178\u7684\u56fe\u904d\u5386\u7b97\u6cd5\uff0c\u5e38\u7528\u4e8e\u751f\u6210\u8ff7\u5bab\u3002\u5b83\u7684\u4e3b\u8981\u4f18\u52bf\u5728\u4e8e\u7b80\u5355\u6613\u61c2\uff0c\u5e76\u80fd\u591f\u751f\u6210\u590d\u6742\u591a\u6837\u7684\u8ff7\u5bab\u7ed3\u6784\u3002<\/p>\n<\/p>\n \u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5\u751f\u6210\u8ff7\u5bab\u7684\u57fa\u672c\u601d\u60f3\u662f\u4ece\u4e00\u4e2a\u8d77\u59cb\u70b9\u51fa\u53d1\uff0c\u901a\u8fc7\u9012\u5f52\u5730\u63a2\u6d4b\u8def\u5f84\uff0c\u521b\u5efa\u51fa\u590d\u6742\u4e14\u591a\u53d8\u7684\u8ff7\u5bab\u7ed3\u6784\u3002\u5177\u4f53\u6b65\u9aa4\u5305\u62ec\uff1a<\/p>\n<\/p>\n \u4ee5\u4e0b\u662f\u4f7f\u7528Python\u5b9e\u73b0\u7684\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5\u751f\u6210\u968f\u673a\u8ff7\u5bab\u7684\u4ee3\u7801\uff1a<\/p>\n<\/p>\n def generate_maze(width, height):<\/p>\n # \u521d\u59cb\u5316\u8ff7\u5bab\uff0c\u6240\u6709\u5899\u58c1\u90fd\u5b58\u5728<\/p>\n maze = [[1 for _ in range(width)] for _ in range(height)]<\/p>\n # \u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5<\/p>\n def dfs(x, y):<\/p>\n # \u968f\u673a\u6253\u4e71\u65b9\u5411<\/p>\n directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]<\/p>\n random.shuffle(directions)<\/p>\n for dx, dy in directions:<\/p>\n nx, ny = x + dx * 2, y + dy * 2<\/p>\n if 0 <= nx < width and 0 <= ny < height and maze[ny][nx] == 1:<\/p>\n maze[ny][nx] = 0<\/p>\n maze[y + dy][x + dx] = 0<\/p>\n dfs(nx, ny)<\/p>\n # \u9009\u62e9\u8d77\u70b9<\/p>\n start_x, start_y = random.randrange(0, width, 2), random.randrange(0, height, 2)<\/p>\n maze[start_y][start_x] = 0<\/p>\n dfs(start_x, start_y)<\/p>\n return maze<\/p>\n def print_maze(maze):<\/p>\n for row in maze:<\/p>\n print(''.join(['#' if cell == 1 else ' ' for cell in row]))<\/p>\n maze = generate_maze(21, 21)<\/p>\n print_maze(maze)<\/p>\n <\/code><\/pre>\n<\/p>\n Prim\u7b97\u6cd5\u662f\u4e00\u79cd\u751f\u6210\u6700\u5c0f\u751f\u6210\u6811\u7684\u7ecf\u5178\u7b97\u6cd5\uff0c\u540c\u6837\u53ef\u4ee5\u5e94\u7528\u4e8e\u8ff7\u5bab\u751f\u6210\u3002\u5b83\u80fd\u6709\u6548\u5730\u751f\u6210\u8def\u5f84\u5747\u5300\u5206\u5e03\u7684\u8ff7\u5bab\u3002<\/p>\n<\/p>\n Prim\u7b97\u6cd5\u751f\u6210\u8ff7\u5bab\u7684\u6838\u5fc3\u601d\u60f3\u662f\u4ece\u4e00\u4e2a\u8d77\u59cb\u70b9\u5f00\u59cb\uff0c\u901a\u8fc7\u4e0d\u65ad\u6269\u5c55\u5f53\u524d\u5df2\u751f\u6210\u7684\u8ff7\u5bab\u8def\u5f84\uff0c\u9010\u6b65\u6253\u901a\u5899\u58c1\u76f4\u81f3\u8986\u76d6\u6574\u4e2a\u8ff7\u5bab\u3002\u5177\u4f53\u6b65\u9aa4\u5305\u62ec\uff1a<\/p>\n<\/p>\n \u4ee5\u4e0b\u662f\u4f7f\u7528Python\u5b9e\u73b0\u7684Prim\u7b97\u6cd5\u751f\u6210\u968f\u673a\u8ff7\u5bab\u7684\u4ee3\u7801\uff1a<\/p>\n<\/p>\n maze = [[1 for _ in range(width)] for _ in range(height)]<\/p>\n walls = []<\/p>\n def add_walls(x, y):<\/p>\n if x > 1: walls.append((x - 2, y, x - 1, y))<\/p>\n if y > 1: walls.append((x, y - 2, x, y - 1))<\/p>\n if x < width - 2: walls.append((x + 2, y, x + 1, y))<\/p>\n if y < height - 2: walls.append((x, y + 2, x, y + 1))<\/p>\n start_x, start_y = random.randrange(0, width, 2), random.randrange(0, height, 2)<\/p>\n maze[start_y][start_x] = 0<\/p>\n add_walls(start_x, start_y)<\/p>\n while walls:<\/p>\n wx, wy, px, py = walls.pop(random.randrange(len(walls)))<\/p>\n if maze[wy][wx] == 1:<\/p>\n maze[wy][wx] = 0<\/p>\n maze[py][px] = 0<\/p>\n add_walls(wx, wy)<\/p>\n return maze<\/p>\n maze_prim = generate_maze_prim(21, 21)<\/p>\n print_maze(maze_prim)<\/p>\n <\/code><\/pre>\n<\/p>\n Kruskal\u7b97\u6cd5\u4e5f\u662f\u4e00\u79cd\u751f\u6210\u6700\u5c0f\u751f\u6210\u6811\u7684\u7b97\u6cd5\uff0c\u9002\u7528\u4e8e\u751f\u6210\u8ff7\u5bab\u3002\u5b83\u901a\u8fc7\u9010\u6b65\u5408\u5e76\u8fde\u901a\u5206\u91cf\uff0c\u5f62\u6210\u5b8c\u6574\u7684\u8ff7\u5bab\u7ed3\u6784\u3002<\/p>\n<\/p>\n Kruskal\u7b97\u6cd5\u751f\u6210\u8ff7\u5bab\u7684\u57fa\u672c\u601d\u60f3\u662f\u5c06\u6240\u6709\u5899\u58c1\u4f5c\u4e3a\u8fb9\u8fdb\u884c\u6392\u5e8f\uff0c\u5e76\u4e0d\u65ad\u9009\u62e9\u6700\u5c0f\u7684\u8fb9\u8fdb\u884c\u5408\u5e76\uff0c\u76f4\u5230\u5f62\u6210\u4e00\u4e2a\u65e0\u73af\u7684\u8fde\u901a\u56fe\u3002\u6b65\u9aa4\u5982\u4e0b\uff1a<\/p>\n<\/p>\n \u4ee5\u4e0b\u662f\u4f7f\u7528Python\u5b9e\u73b0\u7684Kruskal\u7b97\u6cd5\u751f\u6210\u968f\u673a\u8ff7\u5bab\u7684\u4ee3\u7801\uff1a<\/p>\n<\/p>\n if parent[x] != x:<\/p>\n parent[x] = find(parent, parent[x])<\/p>\n return parent[x]<\/p>\n def union(parent, rank, x, y):<\/p>\n rootX, rootY = find(parent, x), find(parent, y)<\/p>\n if rootX != rootY:<\/p>\n if rank[rootX] > rank[rootY]:<\/p>\n parent[rootY] = rootX<\/p>\n elif rank[rootX] < rank[rootY]:<\/p>\n parent[rootX] = rootY<\/p>\n else:<\/p>\n parent[rootY] = rootX<\/p>\n rank[rootX] += 1<\/p>\n def generate_maze_kruskal(width, height):<\/p>\n maze = [[1 for _ in range(width)] for _ in range(height)]<\/p>\n edges = []<\/p>\n parent = {}<\/p>\n rank = {}<\/p>\n for y in range(1, height, 2):<\/p>\n for x in range(1, width, 2):<\/p>\n idx = (y \/\/ 2) * (width \/\/ 2) + (x \/\/ 2)<\/p>\n parent[idx] = idx<\/p>\n rank[idx] = 0<\/p>\n if x < width - 2: edges.append((x, y, x + 2, y))<\/p>\n if y < height - 2: edges.append((x, y, x, y + 2))<\/p>\n random.shuffle(edges)<\/p>\n for x1, y1, x2, y2 in edges:<\/p>\n idx1 = (y1 \/\/ 2) * (width \/\/ 2) + (x1 \/\/ 2)<\/p>\n idx2 = (y2 \/\/ 2) * (width \/\/ 2) + (x2 \/\/ 2)<\/p>\n if find(parent, idx1) != find(parent, idx2):<\/p>\n union(parent, rank, idx1, idx2)<\/p>\n maze[y1][x1] = 0<\/p>\n maze[(y1 + y2) \/\/ 2][(x1 + x2) \/\/ 2] = 0<\/p>\n maze[y2][x2] = 0<\/p>\n return maze<\/p>\n maze_kruskal = generate_maze_kruskal(21, 21)<\/p>\n print_maze(maze_kruskal)<\/p>\n <\/code><\/pre>\n<\/p>\n\u4e00\u3001\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5\u751f\u6210\u8ff7\u5bab<\/strong><\/h2>\n
1\u3001\u7b97\u6cd5\u539f\u7406<\/h2>\n<\/p>\n
\n
2\u3001\u4ee3\u7801\u5b9e\u73b0<\/h2>\n<\/p>\n
import random<\/p>\n\u6253\u5370\u8ff7\u5bab<\/strong><\/h2>\n
\u751f\u6210\u5e76\u6253\u5370\u8ff7\u5bab<\/strong><\/h2>\n
3\u3001\u7b97\u6cd5\u4f18\u7f3a\u70b9<\/h2>\n<\/p>\n
\n
\u4e8c\u3001Prim\u7b97\u6cd5\u751f\u6210\u8ff7\u5bab<\/strong><\/h2>\n
1\u3001\u7b97\u6cd5\u539f\u7406<\/h2>\n<\/p>\n
\n
2\u3001\u4ee3\u7801\u5b9e\u73b0<\/h2>\n<\/p>\n
def generate_maze_prim(width, height):<\/p>\n3\u3001\u7b97\u6cd5\u4f18\u7f3a\u70b9<\/h2>\n<\/p>\n
\n
\u4e09\u3001Kruskal\u7b97\u6cd5\u751f\u6210\u8ff7\u5bab<\/strong><\/h2>\n
1\u3001\u7b97\u6cd5\u539f\u7406<\/h2>\n<\/p>\n
\n
2\u3001\u4ee3\u7801\u5b9e\u73b0<\/h2>\n<\/p>\n
def find(parent, x):<\/p>\n3\u3001\u7b97\u6cd5\u4f18\u7f3a\u70b9<\/h2>\n<\/p>\n