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

引用定向最小生成树问题：      如果有的话，丢弃进入根部的弧线;对于除了之外的每个节点   root，选择进入弧   成本最低;让选中的n-1   弧是集合S.   如果没有形成循环，则G（N，S）是MST。否则，继续。   对于形成的每个循环，将循环中的节点收缩为伪节点   （k），并修改每个弧的成本   它进入循环中的节点（j）   从某个节点（i）循环之外   根据以下等式。   C（I，K）= C（I，J） - （C（X（j）中，j）的-min_ {Ĵ}（C（X（J），J））   这里c（x（j），j）是弧的成本   在进入j的循环中。   对于每个伪节点，选择具有最小值的输入弧   修改成本;更换电弧   进入S中的同一个真实节点   新选择的弧。   使用缩减图表转到步骤2。         该算法的关键思想是   找到有的替换弧   消除的最低额外费用   循环（如果有的话）。给定的等式   展示相关的额外费用。