Минимальный вес связующего дерева для ориентированного графа с параллельными ребрами

Question

Мне бы хотелось, чтобы имя алгоритма можно было использовать для поиска связующего дерева с минимальным весом из направленного циклического графа с параллельными ребрами. Информация о любых библиотеках c ++, которые можно использовать для их получения с помощью анализа времени выполнения и эффективности.

Answer 1

Не существует такого понятия, как минимальное остовное дерево для ориентированных графов. Вы, вероятно, имеете в виду минимальный охват абортов (https://en.wikipedia.org/wiki/Arborescence_(graph_theory)).

Для нахождения минимальной стоимости воздержания существует алгоритм, называемый алгоритмом Чу-Лю / Эдмондса. (https://en.wikipedia.org/wiki/Edmonds%27_algorithm) В зависимости от реализации может быть найдено значение минимальной стоимости в O (VE) или O (E log V) или O (E + V log V).