[Home Page - Algorithms](/@roger61205/Algorithms)
[toc]

Let $G=(V,E)$ be a connected, directed and weighted path.
# Algorithm
Chu-Liu-Edmonds' Algorithm takes the following steps to find a MST in a directed graph:
1. Step 1
Initially, every vertex is considered a subtree. For each subtree, keep 1 incoming edge with the minimum weight.
1. Step 1-1:
If there is no cycle, go to step 2.
2. Step 1-2:
If there is a cycle,
1. Step 1-2-1
Merge subtrees with the cycle into one.
2. Step 1-2-2
For each vertex in the subtree, add the weight of its outgoing edge chain to its incoming edges not in the subtree.
3. Step 1-2-3
Go to step 1.
2. Step 2: Break all cycles by removing edges that cause multiple parents.
# Analysis

**Reference**
[8.4. Edmonds' Algorithm - GitBook](https://emory.gitbook.io/dsa-java/minimum-spanning-trees/edmonds-algorithm)