我希望算法的名称可用于从具有平行边缘的定向循环图中查找最小权重生成树。有关任何c ++库的信息,可用于获取与运行时和效率分析相同的c ++库。
对于有向图,没有最小生成树这样的东西。您可能已经考虑到最小跨越荧光(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。