---
# System prepended metadata

title: Chu-Liu/Edmonds' Algorithm
tags: [Algorithms, Data Structures and Algorithms]

---

[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)