使用Prim算法求有向图的MST

Question

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

Answer 1

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

1. 丢弃进入根部的弧（如果有）；对于除
   root，选择输入弧
   成本最小；令所选的n-1
   弧为集合S。
2. 如果没有形成环，G(N,S)是一个MST。否则，继续。
3. 对于形成的每个循环，将循环中的节点收缩为伪节点
   (k)，并修改每条弧的成本
   进入循环中的节点(j)
   从循环外的某个节点 (i)
   根据以下等式。
   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。

该算法的核心思想是
找到替换弧
消除的最小额外成本
周期（如果有）。给定的方程
显示相关的额外费用。