algorithm - 使用 Prim 算法查找有向图的 MST

Question

任何人都可以帮助我如何使用 PRIM 算法查找 MST。突出显示 MST 的边缘并写下将节点添加到 MST 的顺序。谢谢

Answer 1

引用有向最小生成树问题：

1. 如果有的话，丢弃进入根的弧；对于根以外的每个节点，选择成本最小的进入弧；令选取的 n-1 条弧为集合 S。
2. 如果没有形成循环，则 G(N,S) 是 MST。否则，继续。
3. 对于每个形成的循环，将循环内的节点收缩为伪节点（k），并根据以下公式修改从循环外的某个节点（i）进入循环内节点（j）的每条弧的成本方程。
   c(i,k)=c(i,j)-(c(x(j),j)-min_{j}(c(x(j),j)) 这里 c(x(j),j)是进入 j 的循环中弧的成本。
4. 对于每个伪节点，选择修改成本最小的进入弧；用新选择的弧替换进入 S 中相同实节点的弧。
5. 使用收缩图转到第 2 步。

该算法的关键思想是找到具有最小额外成本的替换弧来消除循环（如果有）。给定的等式显示了相关的额外成本。