当前位置: 首页 > 知识库问答 >
问题:

Prim算法优先级队列

晋奕
2023-03-14

我试图实现Prim的算法Java优先级队列。

我找不到我的错误我只是认识到队列没有正确地排列节点。

图表示例:

0 4 7 5
4 0 2 3
7 2 0 1
5 3 1 0

它始终将节点 4 作为第二个节点。因此,它对队列进行排序,如 [node1, node4, node2, node3],而不是 [node1,node2, node3, node4]。我对优先级队列执行了哪些操作?

问候语

    public class PrimAlgorithm {

        private static int[] par; // parent
        private static int[] key; // value
        private static int sum;


        public static void prim(Graph g){

            Node[] nodes = g.getNodes();
            key = new int[g.getMatrix().length];
            par = new int[g.getMatrix().length];


                    PriorityQueue<Node> queue = new PriorityQueue<Node>(42, new Comparator<Node>(){
                        public int compare(Node v1, Node v2){
                            return Integer.valueOf(key[v1.getId()-1]).compareTo(Integer.valueOf(key[v2.getId()-1]));



            for (Node n : nodes) {
                int x = n.getId()-1;
                key[x] = 1000;
                par[x] = 0; 
                queue.add(n);
            }

            key[0] = 0;


            while(!queue.isEmpty()) {
                Node n = queue.poll();

                List<Node> neighbours = n.getNeighbors();

                for (Node m : neighbours){
                    if ( queue.contains(m) && g.getEdge(n, m).getWeight() !=0 && g.getEdge(n, m).getWeight() < key[m.getId()-1]){

                        par[m.getId()-1] = n.getId();
                        key[m.getId()-1] = g.getEdge(n, m).getWeight();

                    }
                }
            }

            for (int i=0; i < key.length; i++){
                sum += key[i];
              }

            System.out.println("Das Gewicht des minimalen Spannbaumes lautet: " + sum);
            System.out.println("Der Spannbaum ergibt sich wie folgt: " );
            //fängt ab 1 an sonst, hätten wir immer noch einen Nullknoten
            for(int i=0; i <par.length; i++){
                System.out.println("Der Vorgänger von Knoten: "  + " "+ (i+1) + "-> "  +  par[i] + " Gewicht " 
                        + key[i]);
            }

        }

        public static void main(String[] args) {
            System.out.println("Prim Algorithmus zu Berechnung des minimalen Spannbaums.");
            Graph g = new Graph();

            prim(g);
        }

}

共有1个答案

梁丘琛
2023-03-14

一些事情:

    < Li > priority queue的默认实现不能动态地对队列中的项目重新排序。换句话说,当您在中添加项目后更改键时,它不会导致队列中已有的项目更改它们的顺序。 < li >当您第一次将节点添加到PriorityQueue时,它们都具有相同的优先级。因此,根据优先级队列的API,

如果多个元素以最小值绑定,则头部就是这些元素之一——连接被任意破坏。

因此不能保证节点的初始顺序。

对于重新排序队列的有效方法,请注意,添加操作是O(log(n)),这是有效的,而从队列前端以外的任何位置删除操作是O,这应该避免。因此,一个好的技巧是保持一个布尔访问数组,如果节点i已经被处理,则访问数组[i]为真。然后,您可以多次添加同一节点,知道将首先检索具有最低键的节点。如果在轮询某个节点的队列时,visited[node.id]已为true,则只需跳过它即可。

当然,为了使这一点起作用,节点必须基于它包含的某些值而不是外部数组进行比较,这样队列中就可以有两个id相同但键不同的节点。

 类似资料:
  • 我正在为Dikjstra算法做一个优先级队列。我目前在插入方法上有麻烦。我包含了整个类的代码,以防你需要更好地了解我想完成的事情。我将堆索引放在一个数组列表(heapIndex)中,堆放在另一个数组列表中。 那是我运行程序后的输出(值,优先级,堆索引)。*(-1)表示heapIndex中的空单元格。

  • 这是一道古老的考题。 在什么条件下(V, E),我们应该实现的Prim的算法使用数组(索引的顶点)而不是堆(与对数时间实现的提取最小和减少关键操作)的最小优先级队列? 在什么条件下(V,E),我们应该使用有序数组实现Prim算法的最小优先级队列?

  • 我的问题是:每个节点的优先级是什么?我认为它是最小值的传入边缘的权重,但我不确定。这是真的吗? 第二个问题,当我提取队列的根时,如果这个节点不与任何一个被访问的节点邻接,它将如何工作?

  • 有人能帮我找到我的PQ的问题吗?

  • 这是我写的Dijkstra算法的代码: 在这方面我不能理解的工作 这涉及到: < code>()运算符在这里有什么用?我是说它在这段代码中是如何运作的? 还有为什么我们使用

  • 在我实现Dijkstra算法的过程中,我有1个数组(包含所有节点)和1个优先级队列(包含所有节点)。每当一个节点排队时,我都会用新的距离和它来自哪里来更新所有相邻的节点,这样我就可以回溯路径。 优先级队列中的节点更新为新距离,数组中的节点更新为它来自的位置和新距离。当节点出列时,数组中的最终距离会更新: 用前一个节点的信息更新数组和用距离更新优先级队列是否可以接受? 只要找到更好的距离,就会发生这