Finding a minimum spanning tree on a directed graph

algorithm graph minimum-spanning-tree
user3347255 picture user3347255 · Feb 24, 2014 · Viewed 15.9k times · Source

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.

Answer

templatetypedef picture templatetypedef · May 24, 2014

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 questions

Difference between Prim's and Dijkstra's algorithms?

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Read More
Is Minimum Spanning Tree afraid of negative weights?

This is a follow-up question of Why most graph algorithms do not adapt so easily to negative numbers?. I think Shortest Path (SP) has problem with negative weights, because it adds up all weights along the paths and tries to …

Read More
How is a minimum bottleneck spanning tree different from a minimum spanning tree?

A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. A MBST is not necessarily a MST (minimum spanning tree). Please …

Read More