# 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>" %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/minimum-spanning-trees/edmonds-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.