algorithm - 具有平行边的有向图的最小权重生成树

Question

我希望算法的名称可用于从具有平行边的有向循环图中找到最小权重生成树。有关任何可用于获取与运行时和效率分析相同的 c++ 库的信息。

标签： algorithmnetworkinggraph-theorygraph-algorithm

Answer 1

有向图没有最小生成树。您可能想到了最小跨度流产（https://en.wikipedia.org/wiki/Arborescence_(graph_theory)）。

为了找到最小成本流产，有一种称为 Chu-Liu/Edmonds 算法的算法。( https://en.wikipedia.org/wiki/Edmonds%27_algorithm ) 它可以根据实现在 O(VE) 或 O(E log V) 或 O(E + V log V) 中找到最小成本的终止。