Prim
コードについての説明
グラフの最小全域木の重みを求めるアルゴリズム.
最小全域木とはもとのグラフの部分グラフでありかつすべての頂点を含む木のなかで辺の重みの総和が最小のもののことである.
同じく最小全域木を求めるアルゴリズムとして Kruskal 法 がある.
頂点集合 $V= \{ 0 \}$ から始めて, $V$ 内の頂点と隣接する頂点のうちその間の辺の重みが最小であるようなものを新たに $V$ の要素として加えることを繰り返す.
密なグラフ($m = \Theta (n^2)$)については最小重みの辺を優先度付きキューを使わず愚直に計算することで $\O (n^2)$ で解くことができ,
この場合は Kruskal 法 $\O ( n^2 \log n)$ よりも高速に動作する.
また計算量の意味では fibonacci heap を用いた高速化 で $\O (n \log n + m)$ 時間に改善することが可能.
(関数)
add_edge$(u, v, cost)$ : $u, v$ の間に重み $cost$ の無向辺を追加する
solve(): 最小全域木の重みを計算する
時間計算量: $\O (m \log n)$
コード
template<typename T> class Prim {
public:
struct edge{
int to;
T cost;
};
using pti = pair<T, int>;
int V;
vector<vector<edge> > G;
vector<T> d;
vector<bool> used;
Prim(int node_size) : V(node_size), G(V), d(V, numeric_limits<T>::max()), used(V, false){}
void add_edge(int u, int v, T val){
G[u].push_back((edge){v, val}), G[v].push_back((edge){u, val});
}
T solve(){
priority_queue<pti, vector<pti>, greater<pti> > que;
T res = 0;
d[0] = 0;
que.push(pti(0, 0));
while(!que.empty()){
pti p = que.top();
que.pop();
int v = p.second;
if(used[v]) continue;
res += p.first;
used[v] = true;
for(auto& e : G[v]){
if(!used[e.to] && d[e.to] > e.cost){
d[e.to] = e.cost;
que.push(pti(d[e.to], e.to));
}
}
}
return res;
}
};
verify 用の問題
AOJ : Minimum Spanning Tree 提出コード