0Pricing
Competitive Programming Academy · レッスン

Kruskal の最小全域木

サイクルを作らず最も安い辺を追加します

「Kruskal の最小全域木」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

MST とは

最小全域木は、サイクルを作らずに、辺の重みの合計が最小となるようすべての頂点を接続します。町に最小コストで配線するイメージです。🌲

Kruskal法の基本方針

Kruskal法は貪欲法そのものです。サイクルを作らない最も安い辺を、グラフ全体がつながるまで追加し続けます。

ステップ1：辺をソートする

まず、すべての辺を重みの小さい順にソートします。安い辺を貪欲に優先することが、最終的な合計を最小にします。

edges.sort()  # (weight, u, v)

DSU が最適な理由

辺を追加してサイクルができるのは、両端点がすでにつながっている場合だけです。DSUを使えば、この連結性の判定をほぼ定数時間で行えます。🤝

ソート済みの辺をたどる

辺を最も安いものから最も高いものへ順に見ていきます。それぞれについて、2つの端点が DSU 内ですでに同じrootを共有しているか確認します。

for w, u, v in edges:
    ru, rv = find(u), find(v)

採用するか棄却するか

root が異なる場合、その辺は別々の部分をつなぐため、採用して union します。root が同じ場合は、サイクルを避けるためにスキップします。

if ru != rv:
    union(u, v)
    total += w

停止するタイミング

n 個の頂点からなる全域木の辺数は、必ずn - 1本です。その本数を採用したら、そこで処理を早期終了できます。

非連結の検出

すべての辺を見終えた時点で、採用した辺が n - 1 本未満なら、グラフは非連結であり、全域木は存在しません。

計算時間

ソートが支配的なので、Kruskal法の計算量はO(E log E)です。DSU の操作は非常に軽いため、全体の計算量にはほとんど影響しません。

貪欲法が正しい理由

カットの性質により、任意の分割をまたぐ最小の辺は安全に追加できます。これが、最も安い辺から選んでも間違いにならない理由です。

Kruskal法を使う場面

Kruskal法は、辺リストで与えられる疎グラフに適しています。辺リストは、競技プログラミングの問題で直接与えられることが多い形式です。⚡

確認問題

Kruskal法が辺を棄却する条件を考えてみましょう。

振り返り

Kruskal法による MSTを構築しました。辺をソートし、DSU で2つのコンポーネントをつなぐ最も安い辺を追加して、n - 1 本で停止します。🎉

よくある質問

「Kruskal の最小全域木」レッスンは無料ですか？

はい。「Kruskal の最小全域木」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「Kruskal の最小全域木」で何を学びますか？

サイクルを作らず最も安い辺を追加します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「Kruskal の最小全域木」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 経路圧縮付き DSU
  2. ランクによる Union と連結成分
  3. Kruskal の最小全域木
  4. ヒープを使う Prim の MST
← Competitive Programming Academyに戻る