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)

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

Answer 1

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

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