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.
Asked
Active
Viewed 2.8k times
33
-
What steps do you need to take to calculate this value? – Ian R. O'Brien Feb 24 '14 at 15:42
-
Does Kruskal's count as a modified Prim's? – Alejandro Feb 27 '14 at 11:44
-
I was able to solve it. thank you! – user3347255 Feb 28 '14 at 12:19
-
3MST for a directed graph is a different problem. It is the Minimum Cost Arborescence Problem. – Nikunj Banka Mar 23 '14 at 18:40
1 Answers
37
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!
templatetypedef
- 362,284
- 104
- 897
- 1,065
-
3anyone 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. – Jordan Aug 08 '18 at 18:04