最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ？
最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた． 最小全域木について クラスカル法 プリム法 PKUの問題 クラスカル法による解答 プリム法による解答 メモリ使用量と実行時間の比較 最小全域木について まず，全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと．つまり，連結グラフから適当な辺を取り除いていき，閉路をもたない木の形にしたものが全域木となる．ここで，グラフの各辺に重みがある場合，重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という． 最小全域木を求めるアルゴリズムとしては以下の二つが有名である． クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲
Disjoint SetsにおけるUnion Find - ぬいぐるみライフ？
またPKUの問題を解いてみた．今回のテーマはUnion Find． Union Find Disjoint Sets(互いに素な集合)におけるUnion Findとは，指定された二つの要素x，yが同じ集合に含まれるかどうかを調べるアルゴリズムのこと．集合と要素を多分木とその葉で表現し，木の根を集合の代表要素とみなすことによって，二つの要素が同じ集合に含まれるかどうかの判定は代表要素の比較操作に落とすことができる．単純な木を用いた場合は代表要素の検索には最悪O(N)の計算量がかかってしまうが，この木に適当な平衡操作を行うことによって，計算量をO(A(N))に抑えられることが知られている(A(N)はアッカーマン関数の逆関数)． 問題 Problem 2524 - Ubiquitous Religions http://acm.pku.edu.cn/JudgeOnline/problem?id=
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
