Эквивалент MST в ориентированном графе называется оптимальным ветвлением или древовидной структурой с минимальными затратами и существует несколько хорошие алгоритмы для поиска. Наиболее известным, вероятно, является алгоритм Чу-Эдмондса-Лю , который может быть реализован за время O (mn) простым способом и за время O (m + n log n) с использованием более умных структур данных.
Надеюсь, это поможет!