每日算法 — 使用java实现迷宫生成与求解：Kruskal与Prim最小生成树算法

迷宫生成是图论算法最直观、最有趣的应用场景之一。一个完美的迷宫在图论中等价于一棵生成树——从入口到出口有且仅有一条简单路径，且所有格子彼此连通。本文将用Java实现两种经典的最小生成树（MST）算法——Kruskal与Prim——来生成随机迷宫，并配合BFS求解最短路径。你将看到抽象图论如何变成可玩的迷宫世界。

一、图论建模：迷宫即生成树

将迷宫抽象为一张无向图：
– 节点：每个可通行的格子 (x, y)
– 边：相邻两个格子之间的一堵”墙”，打通后形成通路
– 权重：为每条墙分配一个随机权重，确保生成的迷宫具有随机性

完美迷宫的判定条件：
1. 连通性：任意两个格子之间可达（图连通）
2. 无环性：任意两点之间只有唯一路径（无回路，即树结构）

因此，一个 m × n 的迷宫对应一张具有 m × n 个节点、m × n − 1 条边的生成树。

二、核心数据结构

2.1 二维坐标与方向枚举

/**
 * 二维坐标点，表示迷宫中的格子
 */
public record Cell(int x, int y) {
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Cell c)) return false;
        return x == c.x && y == c.y;
    }

    @Override
    public int hashCode() {
        return x * 131 + y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

/**
 * 四个基本方向，用于邻居遍历与墙的打通
 */
public enum Direction {
    UP(0, -1), DOWN(0, 1), LEFT(-1, 0), RIGHT(1, 0);

    public final int dx;
    public final int dy;

    Direction(int dx, int dy) {
        this.dx = dx;
        this.dy = dy;
    }

    /**
     * 返回相反方向，用于双向拆墙
     */
    public Direction opposite() {
        return switch (this) {
            case UP -> DOWN;
            case DOWN -> UP;
            case LEFT -> RIGHT;
            case RIGHT -> LEFT;
        };
    }
}

2.2 并查集（Union-Find）：Kruskal算法的核心

/**
 * 并查集，支持路径压缩与按秩合并
 * 时间复杂度：单次操作近似 O(α(N))，α为阿克曼函数的反函数
 */
public class UnionFind {
    private final int[] parent;
    private final int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    /**
     * 查找根节点，带路径压缩
     */
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩：直接指向根
        }
        return parent[x];
    }

    /**
     * 合并两个集合，按秩合并
     * @return true表示合并成功（原本不在同一集合），false表示已在同一集合（会形成环）
     */
    public boolean union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return false; // 已在同一集合，合并会形成环

        // 按秩合并：将矮树挂到高树下
        if (rank[ra] < rank[rb]) {
            parent[ra] = rb;
        } else if (rank[ra] > rank[rb]) {
            parent[rb] = ra;
        } else {
            parent[rb] = ra;
            rank[ra]++;
        }
        return true;
    }

    /**
     * 检查两个节点是否连通
     */
    public boolean connected(int a, int b) {
        return find(a) == find(b);
    }
}

2.3 墙的定义：连接两个格子的边

/**
 * 迷宫中的一堵"墙"，打通后连通两个相邻格子
 * 作为图论中的边，携带随机权重用于MST算法
 */
public record Wall(Cell a, Cell b, Direction dir, int weight) implements Comparable<Wall> {
    /**
     * 按权重排序，用于Kruskal算法中的最小堆提取
     */
    @Override
    public int compareTo(Wall other) {
        return Integer.compare(this.weight, other.weight);
    }
}

三、Kruskal算法生成迷宫

Kruskal算法的核心思想：按权重从小到大依次选边，如果该边连接的两个节点不在同一连通分量，则打通这堵墙；否则跳过，避免形成环。

当恰好打通了 rows × cols − 1 堵墙时，所有格子连通且无环，即形成一棵生成树——一个完美迷宫。

import java.util.*;

/**
 * Kruskal算法生成器
 * 1. 枚举所有相邻格子对，生成带随机权重的墙列表
 * 2. 按权重排序
 * 3. 用并查集判断是否连通，不连通则拆墙
 */
public class KruskalMazeGenerator {
    private final int rows;
    private final int cols;
    private final Random random = new Random();

    public KruskalMazeGenerator(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
    }

    /**
     * 生成迷宫，返回二维数组表示每个格子的四面墙状态
     * walls[y][x][d] = true 表示该方向有墙（未打通）
     */
    public boolean[][][] generate() {
        // 初始化：所有格子四面都是墙
        boolean[][][] walls = new boolean[rows][cols][4];
        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < cols; x++) {
                Arrays.fill(walls[y][x], true);
            }
        }

        // 收集所有相邻格子对（墙）
        List<Wall> allWalls = new ArrayList<>();
        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < cols; x++) {
                // 只向右和向下生成边，避免重复
                if (x + 1 < cols) {
                    allWalls.add(new Wall(new Cell(x, y), new Cell(x + 1, y), Direction.RIGHT, random.nextInt(10000)));
                }
                if (y + 1 < rows) {
                    allWalls.add(new Wall(new Cell(x, y), new Cell(x, y + 1), Direction.DOWN, random.nextInt(10000)));
                }
            }
        }

        // 按权重升序排序
        Collections.sort(allWalls);

        // 并查集管理连通分量
        UnionFind uf = new UnionFind(rows * cols);
        int edgesAdded = 0;
        int targetEdges = rows * cols - 1; // 生成树需要恰好 N-1 条边

        for (Wall wall : allWalls) {
            if (edgesAdded >= targetEdges) break;

            int idA = wall.a().y() * cols + wall.a().x();
            int idB = wall.b().y() * cols + wall.b().x();

            // 如果两个格子不连通，则打通这堵墙
            if (uf.union(idA, idB)) {
                removeWall(walls, wall.a(), wall.dir());
                removeWall(walls, wall.b(), wall.dir().opposite());
                edgesAdded++;
            }
        }

        return walls;
    }

    /**
     * 移除指定格子的指定方向的墙
     */
    private void removeWall(boolean[][][] walls, Cell cell, Direction dir) {
        walls[cell.y()][cell.x()][dir.ordinal()] = false;
    }
}

Kruskal生成原理图解

四、Prim算法生成迷宫

Prim算法采用贪心策略：从入口格子开始，维护一个”前沿墙”集合（当前树与外部格子之间的所有墙），每次从中选取权重最小的墙打通，将新格子并入树中。

相比Kruskal的全局排序，Prim更类似于”生长”过程——迷宫从起点逐步向外蔓延。

import java.util.*;

/**
 * Prim算法生成器
 * 1. 从起点开始，将其加入生成树
 * 2. 将起点所有相邻墙加入"前沿墙"优先队列
 * 3. 循环：取最小权重前沿墙，若连接新格子则拆墙并入树，并将新格子的墙加入前沿
 */
public class PrimMazeGenerator {
    private final int rows;
    private final int cols;
    private final Random random = new Random();

    public PrimMazeGenerator(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
    }

    public boolean[][][] generate() {
        boolean[][][] walls = new boolean[rows][cols][4];
        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < cols; x++) {
                Arrays.fill(walls[y][x], true);
            }
        }

        boolean[][] inTree = new boolean[rows][cols]; // 标记是否已加入生成树
        PriorityQueue<Wall> frontier = new PriorityQueue<>(); // 前沿墙，按权重排序

        // 从左上角 (0,0) 开始
        Cell start = new Cell(0, 0);
        inTree[start.y()][start.x()] = true;
        addFrontierWalls(start, frontier, inTree);

        int edgesAdded = 0;
        int targetEdges = rows * cols - 1;

        while (!frontier.isEmpty() && edgesAdded < targetEdges) {
            Wall wall = frontier.poll(); // 取出权重最小的前沿墙
            Cell inside = inTree[wall.a().y()][wall.a().x()] ? wall.a() : wall.b();
            Cell outside = inTree[wall.a().y()][wall.a().x()] ? wall.b() : wall.a();

            // 如果outside已经在树中，跳过（避免成环）
            if (inTree[outside.y()][outside.x()]) continue;

            // 拆墙，将outside加入树
            removeWall(walls, inside, wall.dir());
            removeWall(walls, outside, wall.dir().opposite());
            inTree[outside.y()][outside.x()] = true;
            edgesAdded++;

            // 将新格子的相邻墙加入前沿
            addFrontierWalls(outside, frontier, inTree);
        }

        return walls;
    }

    /**
     * 将cell的所有不在树中的邻居对应的墙加入前沿队列
     */
    private void addFrontierWalls(Cell cell, PriorityQueue<Wall> frontier, boolean[][] inTree) {
        for (Direction dir : Direction.values()) {
            int nx = cell.x() + dir.dx;
            int ny = cell.y() + dir.dy;
            if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && !inTree[ny][nx]) {
                frontier.offer(new Wall(cell, new Cell(nx, ny), dir, random.nextInt(10000)));
            }
        }
    }

    private void removeWall(boolean[][][] walls, Cell cell, Direction dir) {
        walls[cell.y()][cell.x()][dir.ordinal()] = false;
    }
}

Kruskal vs Prim 生成效果对比

五、BFS求解最短路径

生成迷宫后，求解从入口 (0,0) 到出口 (cols-1, rows-1) 的最短路径。由于迷宫是树结构（无环），BFS与DFS找到的路径长度相同，但BFS能保证找到最短路径的通用性。

import java.util.*;

/**
 * BFS求解器：在迷宫中找到从起点到终点的最短路径
 */
public class MazeSolver {

    /**
     * 使用BFS寻找最短路径
     * @param walls 迷宫墙状态
     * @param start 起点
     * @param end 终点
     * @return 路径上的格子列表（包含起点和终点），不可达返回空列表
     */
    public List<Cell> solve(boolean[][][] walls, Cell start, Cell end) {
        int rows = walls.length;
        int cols = walls[0].length;

        boolean[][] visited = new boolean[rows][cols];
        Map<Cell, Cell> parent = new HashMap<>(); // 记录路径来源，用于回溯
        Queue<Cell> queue = new LinkedList<>();

        queue.offer(start);
        visited[start.y()][start.x()] = true;

        while (!queue.isEmpty()) {
            Cell current = queue.poll();

            if (current.equals(end)) {
                return reconstructPath(parent, start, end);
            }

            // 遍历四个方向，检查是否有墙阻挡
            for (Direction dir : Direction.values()) {
                if (walls[current.y()][current.x()][dir.ordinal()]) {
                    continue; // 有墙，不能走
                }

                int nx = current.x() + dir.dx;
                int ny = current.y() + dir.dy;

                if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && !visited[ny][nx]) {
                    Cell next = new Cell(nx, ny);
                    visited[ny][nx] = true;
                    parent.put(next, current);
                    queue.offer(next);
                }
            }
        }

        return Collections.emptyList(); // 不可达（理论上完美迷宫不会不可达）
    }

    /**
     * 根据parent映射回溯路径
     */
    private List<Cell> reconstructPath(Map<Cell, Cell> parent, Cell start, Cell end) {
        List<Cell> path = new ArrayList<>();
        Cell current = end;
        while (!current.equals(start)) {
            path.add(current);
            current = parent.get(current);
        }
        path.add(start);
        Collections.reverse(path);
        return path;
    }
}

六、迷宫渲染与主程序

/**
 * 控制台迷宫渲染器，支持显示迷宫结构和求解路径
 */
public class MazeRenderer {

    /**
     * 渲染迷宫，可选高亮路径
     */
    public void render(boolean[][][] walls, List<Cell> path) {
        int rows = walls.length;
        int cols = walls[0].length;
        Set<Cell> pathSet = new HashSet<>(path);

        // 顶部边界
        printHorizontalBorder(cols);

        for (int y = 0; y < rows; y++) {
            // 每行的左墙和内部垂直墙
            StringBuilder line = new StringBuilder("|");
            for (int x = 0; x < cols; x++) {
                if (pathSet.contains(new Cell(x, y))) {
                    line.append("*"); // 路径标记
                } else {
                    line.append(" ");
                }
                // 右侧是否有墙
                if (walls[y][x][Direction.RIGHT.ordinal()]) {
                    line.append("|");
                } else {
                    line.append(" ");
                }
            }
            System.out.println(line);

            // 底部水平墙
            StringBuilder bottom = new StringBuilder("+");
            for (int x = 0; x < cols; x++) {
                if (walls[y][x][Direction.DOWN.ordinal()]) {
                    bottom.append("-+");
                } else {
                    bottom.append(" +");
                }
            }
            System.out.println(bottom);
        }
    }

    private void printHorizontalBorder(int cols) {
        StringBuilder top = new StringBuilder("+");
        for (int x = 0; x < cols; x++) {
            top.append("-+");
        }
        System.out.println(top);
    }
}

6.1 主程序入口

/**
 * 迷宫生成与求解主程序
 */
public class MazeApp {
    public static void main(String[] args) {
        int rows = 15;
        int cols = 25;

        System.out.println("=== Kruskal 算法生成迷宫 ===");
        boolean[][][] kruskalWalls = new KruskalMazeGenerator(rows, cols).generate();
        solveAndRender(kruskalWalls, rows, cols);

        System.out.println("\n=== Prim 算法生成迷宫 ===");
        boolean[][][] primWalls = new PrimMazeGenerator(rows, cols).generate();
        solveAndRender(primWalls, rows, cols);
    }

    private static void solveAndRender(boolean[][][] walls, int rows, int cols) {
        Cell start = new Cell(0, 0);
        Cell end = new Cell(cols - 1, rows - 1);

        MazeSolver solver = new MazeSolver();
        List<Cell> path = solver.solve(walls, start, end);

        System.out.println("路径长度: " + path.size() + " 步");
        new MazeRenderer().render(walls, path);
    }
}

七、项目结构

maze-mst/
├── src/
│   ├── model/
│   │   ├── Cell.java
│   │   ├── Direction.java
│   │   └── Wall.java
│   ├── algorithm/
│   │   ├── UnionFind.java
│   │   ├── KruskalMazeGenerator.java
│   │   ├── PrimMazeGenerator.java
│   │   └── MazeSolver.java
│   └── game/
│       ├── MazeRenderer.java
│       └── MazeApp.java
└── README.md

八、算法复杂度分析

其中 N = rows × cols 为格子总数，E ≈ 2N 为墙的总数。

九、扩展方向

• 多终点迷宫：生成树不变，从起点到多个终点的路径天然唯一且不交叉
• 带权最短路径：给不同地形赋予通行代价，用Dijkstra替代BFS
• 3D迷宫：将二维网格扩展到三维立方体，MST算法依然适用
• 迷宫难度评估：基于路径长度、转弯次数、死胡同数量等指标量化迷宫难度
• 可视化增强：使用JavaFX或Swing实现交互式迷宫生成动画，直观展示Kruskal与Prim的”生长”差异

十、总结

本文以迷宫生成为切入点，展示了最小生成树算法在实际问题中的优美应用：

1. Kruskal算法通过全局排序与并查集，像”拼图”一样将分散的格子逐步连接成一棵生成树
2. Prim算法从起点出发，以贪心策略不断扩展”前沿”，像”藤蔓”一样向外蔓延
3. BFS在生成的树结构中高效求解唯一最短路径

两种MST算法生成的迷宫在宏观统计上同样随机，但在微观结构上各有特色：Kruskal更加均匀，Prim更具”生长感”。掌握它们，你就拥有了一套将抽象图论转化为可玩迷宫的完整工具链。