Finding a minimum spanning tree on a directed graph
21,945
The equivalent of a minimum spanning tree in a directed graph is called an optimum branching or a minimum-cost arborescence. The classical algorithm for solving this problem is the Chu-Liu/Edmonds algorithm. There have been several optimized implementations of this algorithm over the years using better data structures; the best one that I know of uses a Fibonacci heap and runs in time O(m + n log n) and is due to Galil et al.
Hope this helps!
Related videos on Youtube
Author by
user3347255
Updated on July 18, 2022Comments
-
user3347255 almost 2 years
What algorithm can I use to find a minimum spanning tree on a directed graph? I tried using a modification of Prim's algorithm, but wasn't able to make it work.
-
Ian R. O'Brien over 10 yearsWhat steps do you need to take to calculate this value?
-
Alejandro over 10 yearsDoes Kruskal's count as a modified Prim's?
-
user3347255 over 10 yearsI was able to solve it. thank you!
-
Nikunj Banka over 10 yearsMST for a directed graph is a different problem. It is the Minimum Cost Arborescence Problem.
-
-
Jordan almost 6 yearsanyone happen to know of an implementation of this? I've found limited implementations of the Chu-Liu/Edmonds algorithm, but nothing for the algorithm by Galil et al.