Prim的算法何时分别使用数组和优先级队列？
这是一道古老的考题。
在什么条件下（V， E），我们应该实现的Prim的算法使用数组（索引的顶点）而不是堆（与对数时间实现的提取最小和减少关键操作）的最小优先级队列？
在什么条件下（V，E），我们应该使用有序数组实现Prim算法的最小优先级队列？
共有2个答案
当E很大时，最好为优先级队列使用堆，因为队列中会有很多节点。从数组O（n）/O（n）中查找min/删除min需要时间，而堆只需要O（1）/log（n）。
如果E很小，那么队列中的节点就很少，因此，在这种情况下，找到min并将其从数组中移除不需要很多操作。在这种情况下，没有必要使用堆，甚至可能比数组慢，因为构建堆需要一些操作。
Prim在O（mlog（n））时间内运行，其中m是边的#，n是顶点的35;。然而，当一个图非常稠密时，m非常大，则Prim在O（n^2log（n））中运行。您可以创建一个具有大量（n）个顶点的图，并将所有顶点相互连接，以证明这一点。所以…（n-1）（n-2）（n-3）…（n-n1）。
这可以重写为
n(n 1)/2，这是O(n^2)记录在
优先级队列数组实现在O（n^2）时间内运行，这在wikipedia页面上有记录，尽管我没有证据。
所以当m很大时，最好使用邻接矩阵。
你要求一个条件，我会说当m非常大并且与n的顺序相同时。
-
我试图实现Prim的算法Java优先级队列。 我找不到我的错误我只是认识到队列没有正确地排列节点。 图表示例： 它始终将节点 4 作为第二个节点。因此，它对队列进行排序，如 [node1， node4， node2， node3]，而不是 [node1，node2， node3， node4]。我对优先级队列执行了哪些操作？ 问候语
-
我正在为Dikjstra算法做一个优先级队列。我目前在插入方法上有麻烦。我包含了整个类的代码，以防你需要更好地了解我想完成的事情。我将堆索引放在一个数组列表(heapIndex)中，堆放在另一个数组列表中。 那是我运行程序后的输出(值，优先级，堆索引)。*(-1)表示heapIndex中的空单元格。
-
我需要使用Java中的优先级队列实现Dijkstra的算法。这是我到目前为止的代码： 我需要填写最短路径方法并返回节点数组。但是，我不确定如何做到这一点。我知道我需要在某个时候进行优先排队，但有人可以向我解释一下如何吗？我已经制作了startNode，我知道我需要为它分配一个距离值0，其余节点的距离值为无穷大。另外，可比性从何而来？
-
我正在使用优先级队列实现Dijkstra的算法，我想要一个函数从堆中删除一个元素，但我只能从Dijkstra的主节点索引中向它发送顶点索引，我找不到它在堆上的位置，我负担不起进行二进制搜索。有什么想法吗？
-
这是我写的Dijkstra算法的代码: 在这方面我不能理解的工作 这涉及到: < code>()运算符在这里有什么用？我是说它在这段代码中是如何运作的？ 还有为什么我们使用
-
在我实现Dijkstra算法的过程中，我有1个数组（包含所有节点）和1个优先级队列（包含所有节点）。每当一个节点排队时，我都会用新的距离和它来自哪里来更新所有相邻的节点，这样我就可以回溯路径。 优先级队列中的节点更新为新距离，数组中的节点更新为它来自的位置和新距离。当节点出列时，数组中的最终距离会更新： 用前一个节点的信息更新数组和用距离更新优先级队列是否可以接受？ 只要找到更好的距离，就会发生这