Menu
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.
1000
A directed spanning tree of G is a spanning tree in which no two arcs share their tails. Each vertex is the tail of exactly one arc of the directed spanning tree except for a special vertex r. We call r the root of the spanning tree. Directed spanning trees have been studied in many fields.
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
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!
109
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
