クラスカル法
重み付き連結グラフ P {\displaystyle P} があり、クラスカル法で生成した P {\displaystyle P} の部分グラフを Y {\displaystyle Y} とする。常に異なる2つの木を連結する辺を加えているので、 Y {\displaystyle Y} には閉路がない。また、 Y {\displaystyle Y} の2つの部分を連結する辺を全て選んでいるので、全頂点は連結されている。したがって Y {\displaystyle Y} は P {\displaystyle P} の全域木である。
このアルゴリズムは、1956年にジョゼフ・クラスカル(英語版)が Proceedings of the American Mathematical Society で発表した (pp. 48–50)。
クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法、逆削除法(英語版)、ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含む木で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」(それぞれの連結部分の最小全域木の集合)を求められる。