> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/minimum-spanning-trees/edmonds-algorithm.md).

# 8.4. Edmonds' Algorithm

Chu-Liu-Edmonds' Algorithm takes the following steps to find a MST in a directed graph:

1. Initially, every vertex is considered a subtree.
2. For each subtree, keep 1 incoming edge with the minimum weight.
3. If there is no cycle, go to #5.
4. If there is a cycle,
   1. Merge subtrees with the cycle into one and update scores for all incoming edges to this merged subtree, and goto #2.
   2. For each vertex in the subtree, add the weight of its outgoing edge chain to its incoming edges not in the subtree.
5. Break all cycles by removing edges that cause multiple parents.

The following demonstrates how Chu-Liu-Edmonds' Algorithm find a minimum spanning tree:

{% embed url="<https://www.slideshare.net/jchoi7s/chiliuedmonds-algorithm>" %}

> What is the logic behind updating the edge weights related to the cycles?

The following explains the weight updates in details:

{% embed url="<https://www.slideshare.net/jchoi7s/chiliuedmonds-algorithm-weight-update>" %}