8.4. Edmonds' Algorithm

This section discusses Chu-Liu-Edmonds' Algorithm that finds a MST in a directed graph.

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:

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

The following explains the weight updates in details: