Motivation

クルスカール法は、選択された辺の成長する森を union-find 構造で保持します。辺を安全に追加するために、2つの端点がすでに同じ集合に含まれているかどうか（同じ集合にあればサイクルが形成されるため）を確認します。

なぜクルスカール法を学ぶのか？

• 現実のMST: ネットワーク設計、クラスタリング、最小コストでのケーブル敷設や道路建設など。
• Union-find: コンピュータサイエンスの至る所に登場する、連結性を追跡するための美しく再利用可能な構造です。
• 貪欲法の正当性: 常に最も安価で安全な選択肢を取ることが、全体的な最適解をもたらすもう一つの例です。

グラフのすべての最小全域木は、辺の重みの同じマルチセットを使用するため、合計の重み（および最大の辺）は一意になります。