[競プロ用]最小全域木まとめ - Qiita

最小全域木を求める手法 プリム法 クラスカル法 使い分け 議論になっていた https://togetter.com/li/776049 入力形式で使い分ける？ ノード間のコストが行列で渡される → プリム法 2点のノードとそのコストの組み合わせで渡される。 → クラスカル法 プリム法 任意のスタート地点から始める。 移動可能なノードのうち最も低コストで移動できるものを選び繋ぐ。 2を繰り返し、全てのノードを繋いだ時点で最小全域木となる。 どうすればいいか ノードを繋ぐ度に選択肢が広がっていき、常にその中で最小のものを選択したい。 → 優先度付きキュー(heapq)を用いる。 heapqにタプルを渡すと一番目の要素で最小値を判断されることを利用する。 何がいいのか O(ElogV)。 フィボナッチヒープを使うとより早い？ イメージ 使用例 AOJ ALDS1_12_A import hea