In Arborescence
Cycle
Contracted Node
Min Incoming Edge
Root
Edmonds' Algorithm
Finds minimum spanning arborescence (directed MST) rooted at a specified vertex. Works by selecting min incoming edges and contracting cycles.
Finds minimum spanning arborescence (directed MST) rooted at a specified vertex. Works by selecting min incoming edges and contracting cycles.
Example Graph
Algorithm Phase
Select
Contract
Expand
Controls
Click "Step" to begin finding the minimum arborescence
Statistics
0
Total Weight
0
Contractions
0
Edges Selected
0
Steps