图论为什么我在Java中实现的随机化Prim算法只生成一个完整的网格？

Question

我试图在wikipediahttps://en.wikipedia.org/wiki/Maze_generation_algorithmRandomized_Prim的_算法上遵循这个伪代码 但我的代码只是生成了一个完整的网格。在我对算法的理解中，我似乎遗漏了一些东西。有人能解释一下我做错了什么吗

我看了一些资料，但我无法理解

public class MazeGen {
private int dimension, nodeCounter;
private Node[][] nodes;
private List<Edge> walls;

public static void main(String[] args) {
    MazeGen g = new MazeGen(20);
    g.generate();
    g.printMaze();
}

private void generate() {
    pickCell();
    generateMaze();
}

private void generateMaze() {
    while (!walls.isEmpty()) {
        int v;
        Edge wall = walls.get(ThreadLocalRandom.current().nextInt(walls.size()));
        if ((!wall.nodes[0].visited && wall.nodes[1].visited)
                || (wall.nodes[0].visited && !wall.nodes[1].visited)) {
            if (!wall.nodes[0].visited)
                v = 0;
            else
                v = 1;

            includeNode(wall.nodes[v]);
            wall.nodes[Math.abs(v - 1)].visited = true;
        }
        walls.remove(wall);
    }
}

private void pickCell() {
    int i = ThreadLocalRandom.current().nextInt(dimension);
    int j = ThreadLocalRandom.current().nextInt(dimension);

    includeNode(nodes[i][j]);
}

private void includeNode(Node node) {
    node.visited = true;
    node.partOfMaze = true;
    walls.addAll(node.edges);
}

public void printMaze() {
    for (int i = 0; i < dimension; i++) {
        System.out.println();
        for (int j = 0; j < dimension; j++) {
            if (nodes[i][j].partOfMaze) {
                System.out.print(".");
            } else
                System.out.print("p");
        }
    }
}

public MazeGen(int n) {
    nodes = new Node[n][n];
    walls = new ArrayList<Edge>();
    dimension = n;

    createNodes();
    connectAdjacents();
}

private void connectAdjacents() {
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            verifyConnection(i, j, i, j + 1);
            verifyConnection(i, j, i + 1, j);
        }
    }
}

private void verifyConnection(int i, int j, int arg1, int arg2) {
    if (arg1 < dimension && arg2 < dimension)
        connect(i, j, arg1, arg2);
}

private void createNodes() {
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            nodes[i][j] = new Node();
        }
    }
}

private void connect(int row, int col, int row2, int col2) {
    nodes[row][col].edges.add(new Edge(nodes[row][col], nodes[row2][col2]));
    nodes[row2][col2].edges.add(new Edge(nodes[row][col], nodes[row2][col2]));
}

private class Node {
    boolean visited, partOfMaze;
    int number;
    List<Edge> edges;

    Node() {
        number = nodeCounter++;
        edges = new ArrayList<Edge>();
    }

    @Override
    public String toString() {
        return String.valueOf(number);
    }
}

private class Edge {
    Node[] nodes;

    Edge(Node n, Node n2) {
        nodes = new Node[2];
        nodes[0] = n;
        nodes[1] = n2;
    }

    @Override
    public String toString() {
        return nodes[0] + "-" + nodes[1];
    }
}

Answer 1

忘了维基百科吧，他们审查言论自由，操纵信息，尤其是在政治和社会领域。出于这个原因，我还删除了我在维基百科“迷宫生成”页面上添加的所有内容（见页面历史）

“Prim”MST算法的思想是在断开连接的子图之间保持“切割”（一组边），并始终选择最便宜的边来连接这些子图。标记访问的顶点以避免生成循环

这可以用于迷宫生成，方法是在全网格图中使用边随机权重，或者从空网格图开始，动态添加随机权重边

有关详细信息，请参阅my GitHub repository on maze generation：

https://github.com/armin-reichert/mazes

https://github.com/armin-reichert/mazes/blob/master/mazes-algorithms/src/main/java/de/amr/maze/alg/mst/PrimMST.java

public void createMaze(int x, int y) {
        cut = new PriorityQueue<>();
        expand(grid.cell(x, y));
        while (!cut.isEmpty()) {
            WeightedEdge<Integer> minEdge = cut.poll();
            int u = minEdge.either(), v = minEdge.other();
            if (isCellUnvisited(u) || isCellUnvisited(v)) {
                grid.addEdge(u, v);
                expand(isCellUnvisited(u) ? u : v);
            }
        }
    }

    private void expand(int cell) {
        grid.set(cell, COMPLETED);
        grid.neighbors(cell).filter(this::isCellUnvisited).forEach(neighbor -> {
            cut.add(new WeightedEdge<>(cell, neighbor, rnd.nextInt()));
        });
    }

Answer 2

我认为你的算法是正确的，但你没有保持正确的输出。 所有节点都应该是迷宫的一部分。应成为迷宫一部分的墙是在处理访问的两个节点时连接它们的墙

制作另一个输出墙数组，并在generateMaze方法中设置值

private void generateMaze() {
    while (!walls.isEmpty()) {
        int v;
        Edge wall = walls.get(ThreadLocalRandom.current().nextInt(walls.size()));
        if ((!wall.nodes[0].visited && wall.nodes[1].visited)
                || (wall.nodes[0].visited && !wall.nodes[1].visited)) {
            if (!wall.nodes[0].visited)
                v = 0;
            else
                v = 1;

            includeNode(wall.nodes[v]);
            wall.nodes[Math.abs(v - 1)].visited = true;
            /////////////////////////////////////
            // remove this wall from the output walls
            /////////////////////////////////////
        } else {
            ////////////////////////////////
            // add this wall to the output walls
            ////////////////////////////////
        }
        walls.remove(wall);
    }
}