use*_*255 16 algorithm graph minimum-spanning-tree
我可以使用什么算法在有向图上找到最小生成树？我尝试使用Prim算法的修改,但无法使其工作.
tem*_*def 15
有向图中等效的最小生成树称为最佳分支或最小成本的树枝.解决这个问题的经典算法是Chu-Liu/Edmonds算法.多年来,使用更好的数据结构已经有几种优化的算法实现; 我所知道的最好的一个使用Fibonacci堆并且在时间O(m + n log n)运行并且由Galil等人提出.
希望这可以帮助!