java - 我的 Prim 算法无法正确生成迷宫

Question

我正在尝试使用 Prim 算法实现一个随机生成的迷宫。但是该程序无法正确生成迷宫。请看看并给我一些建议

这是我的迷宫图片:

迷宫应该是这样的: Prim 算法:

private void Prims(){
            List<Vertex> res = new ArrayList<>();
            PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>(CostComparator.compare_W());
            for (int i = 0; i < grids.length; i++){
                for(int j = 0; j < grids[i].length; j++){
                    priorityQueue.offer(grids[i][j]);
                }
            }
            grids[0][0].setG(0);
            while(!priorityQueue.isEmpty()){
                Vertex current = priorityQueue.poll();
                if(current.getPrevious() != null){
                    res.add(current);
                }
                for(Edge edge: current.getEdges()){
                    Vertex destination = edge.getDestination();
                    if(priorityQueue.contains(destination) && destination.getG() > edge.getWeight()){
                        destination.setPrevious(current);
                        destination.setG(edge.getWeight());
                    }
                }
            }
            for(int i = 0; i < res.size(); i++){
                if(i % 2 == 0){
                    res.get(i).setStyle(3);
                }
            }
            update(5);
        }

顶点类:

public class Vertex {
    private int x, y, style;
    private int f, h, g;
    private Vertex previous;
    private List<Edge> edges;
    private boolean isVisited;
}

边缘类:

public class Edge {
    private int weight;
    private Vertex destination;
    private Vertex start;
}

我也看了这篇文章Implementing a randomly generated maze using Prim's Algorithm ，但我仍然无法解决我的问题。我看到@Hoopje在那篇帖子里说，如果两个坐标都是偶数，那么这个单元格一定是一个段落。否则就是墙。然而，当我把它画出来时，它是不正确的，因为它看起来像一个棋盘。谢谢。

Answer 1

Java 的 PriorityQueue<T>当您在松弛期间更改顶点的权重时，不会自动更新其内部状态。解决方案是 remove and re-insert the vertex每当你改变它的重量时。

这可能不是唯一的问题，但对我来说，仅从您的代码来看，这是最明显的问题。