在有向图上寻找最小生成树 [英] Finding a minimum spanning tree on a directed graph

问题描述

我可以使用什么算法在有向图上找到最小生成树？我尝试使用Prim算法的修改，但无法使其工作。

What algorithm can I use to find a minimum spanning tree on a directed graph? I tried using a modification of Prim's algorithm, but wasn't able to make it work.

推荐答案

等价于最小生成有向图中的树被称为最优分支或最小代价树状结构。解决这个问题的经典算法是 Chu-Liu / Edmonds 算法。多年来，这种算法已经有了几种优化实现，使用更好的数据结构;我所知道的最好的一个使用斐波那契堆并且在时间O（m + n log n）中运行，并且由于 Galil等人

The equivalent of a minimum spanning tree in a directed graph is called an optimum branching or a minimum-cost arborescence. The classical algorithm for solving this problem is the Chu-Liu/Edmonds algorithm. There have been several optimized implementations of this algorithm over the years using better data structures; the best one that I know of uses a Fibonacci heap and runs in time O(m + n log n) and is due to Galil et al.

希望这有助于您！

这篇关于在有向图上寻找最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！