Loading...
AlgoNote
/
グラフ
/
基本アルゴリズム
/
クラスカルMST
ja
ログイン
プレビュー
全20ステップ中6ステップのみ表示
ログインして全て見る
可視化
コード
1
/
20
0.5x
1x
1.5x
2x
⏮
◀
▶
▶
⏭
Loading...
🌳
最小全域木を探す!
全都市を最小コストで繋げましょう!最も安い道路から選びます!
基礎学習
クラスカルMST
📖
概念
🎯
活用
⚙️
操作
定義
クラスカルは「最も安いケーブルから」選択して全都市を繋ぐアルゴリズムです。サイクルさえなければOK!
主な特性
✓
貪欲法：毎回最安の辺を選択
✓
Union-Findでサイクル判定 O(α(n))
✓
疎グラフで効率的
✓
O(E log E) 時間計算量
時間計算量
最良
O(E log E)
平均
O(E log E)
最悪
O(E log E)
空間計算量
O(V)
可視化を開始
クラスカルMST | AlgoNote