java - Prim算法的实现

Question

对于我的 CS 类，我需要在 Java 中实现 Prim 的算法，但我在优先级队列步骤中遇到了问题。我有使用优先级队列的经验，并且了解它们通常可以正常工作，但我在执行特定步骤时遇到了问题。

Prim(G,w,r)
  For each u in V[G]
    do key[u] ← ∞ 
       π[u] ← NIL  
  key[r] ← 0
  Q ← V[G]  
  While Q ≠ Ø
    do u ← EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

我创建了一个包含键值(我假设是连接到节点的最轻边)和父节点的节点类。我的问题是我不明白将节点添加到优先级队列中。当父级设置为 NIL 且键设置为 ∞ 时，将所有节点添加到优先级队列对我来说没有意义。

Answer 1

在你问题的伪代码中，key[u] 和 π[u] 是代表 G 的最小生成树的一组值 当算法完成时。在算法开始时，这些值分别被初始化为∞和NIL，表示还没有顶点被添加到MST。下一步设置根元素 (key[r] ← 0)。

优先级队列Q是一个独立于key和π的数据结构。 Q 应使用原始图 G 中的所有顶点进行初始化，而不是键和 π 中的值。请注意，您将需要更多信息，而不仅仅是每个顶点的最亮边和父节点，因为您需要知道与从 Q 中提取的每个顶点相邻的所有顶点。