最小全域木（MST） は、グラフ上のすべての頂点を含みつつ、辺の重みの合計を最小にする木構造です。
クラスカル法 は、最小全域木を効率的に求めるアルゴリズムです。
この記事では競プロ用にC++で実装したライブラリを紹介します。
※なお、今回のライブラリは Graph と UnionFind が前提となっています。
以下リンクからコピペしてご使用ください↓
・グラフ構造体 をC++で実装してみた
・Union-Find をC++で実装してみた
主な機能と計算量
| 名前 | 説明 | 計算量 |
|---|---|---|
kruskal(g) |
グラフに対して、最小全域木を返す | $O(E log E)$ |
C++による実装
//-------Graphのライブラリ----- -//
// //
//-----------------------------//
//-----UnionFindのライブラリ-----//
// //
//-----------------------------//
//0 ~ N-1までのグラフ（連結）の中で、最小全域木を作る
template<typename T = long long>
Graph<T> kruskal(Graph<T> &g){
//連結の判定にはUnion-Findを使う
UnionFind uf(g.size_n());
//辺集合を取得して、コストが小さい順に並び替えておく
vector<typename Graph<T>::Edge> edges = g.edges();
sort(edges.begin(), edges.end());
//コストが小さい順に、連結していない二つを連結するように辺を追加していく
Graph<T> ret(g.size_n());
for(auto &edge: edges){
if(!uf.is_same(edge.u, edge.v)){
uf.unite(edge.u, edge.v);
ret.add_edge(edge.c, edge.u, edge.v);
}
}
return ret;
}
使い方
#include<bits/stdc++.h>
using namespace std;
//--ここにKruskalのライブラリ--//
// //
//--------------------------//
int main(void){
// グラフの作成
Graph g(4);
g.add_edge(10, 0, 1); //0 → 1：コスト10の辺を追加
g.add_edge(10, 0, 2); //0 → 2：コスト10の辺を追加
g.add_edge(15, 0, 3); //0 → 3：コスト15の辺を追加
g.add_edge(10, 2, 3); //2 → 3：コスト10の辺を追加
//最小全域木を求める
Graph mst = kruskal(g);
cout << mst.total_edge_cost() << endl; // 30
}
注意点・Tips
- 頂点番号は
0-indexedで扱っています - クラスカル法のアルゴリズム自体を詳しく知りたい方はクラスカル法による最小全域木を求めるアルゴリズムなどがわかりやすいです
- 最小全域木を求めるアルゴリズムは他にもあり、プリム法などが有名です
実際に使ってみる
典型アルゴリズム問題集 - F問題
#include<bits/stdc++.h>
using namespace std;
//--ここにUnionFindライブラリ--//
// //
//--------------------------//
//--ここにKruskalのライブラリ--//
// //
//--------------------------//
//グローバル変数
int N, M;
int main(void){
// 入力
cin >> N >> M;
// グラフを初期化
Graph g(N);
//グラフを構築
for(int i=0;i<M;i++){
//辺の情報を入力
int u, v, c;
cin >> u >> v >> c;
// 無向辺としてグラフに追加
g.add_edge(c, u, v);
g.add_edge(c, v, u);
}
//最小全域木を求める
Graph mst = kruskal(g);
cout << mst.total_edge_cost() << endl;
}