<ul>
<li>Algorithm for finding the <a href="/en/minimum%20area%20tree">minimum area tree</a> of an undirected connected graph
</li>
<li>O(E log E)
</li>
<li>Add the cost of the sides from the cheapest to the least expensive to avoid creating a closed channel.
<ul>
<li>This closed path can be determined in almost constant time by using [UnionFind</li>
<li>O(E log E) where the edges are sorted by cost.<ul>
<li>O(E) if sorted or <a href="/en/linear%20time%20sort">linear time sort</a> if possible</li>
</ul>
</li>
</ul>
</li>
<li><a href="https://dai1741.github.io/maximum-algo-2012/docs/minimum-spanning-tree/">Minimum Global Tree (Kruskal Method and UnionFind) - Algorithm Workshop</a>
</li>
<li><a href="https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AB%E3%83%AB%E6%B3%95">Kruskal Act - Wikipedia</a>
</li>
</ul>
<hr>
This page is auto-translated from <a href="https://scrapbox.io/nishio/%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AB%E3%83%AB%E6%B3%95">/nishio/クラスカル法</a> using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.

Kruskal method