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

问题描述 投票:0回答:1

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

algorithm networking graph-theory graph-algorithm
1个回答
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)中找到最低成本的aborescne。

© www.soinside.com 2019 - 2024. All rights reserved.