Ответ 1
Эквивалент минимального остовного дерева в ориентированном графе называется оптимальным ветвлением или минимальным сечением. Классическим алгоритмом решения этой проблемы является алгоритм Chu-Liu/Edmonds. На протяжении многих лет было реализовано несколько оптимизированных реализаций этого алгоритма с использованием лучших структур данных; лучший из которых, который я знаю, использует кучу Фибоначчи и работает во времени O (m + n log n) и обусловлен Galil et al.
Надеюсь, это поможет!