algorithm
Kruskalのアルゴリズム
サーチ…
備考
Kruskalのアルゴリズムは、グラフの最小スパニングツリー（MST）を見つけるために使用される欲張りアルゴリズムです。最小スパニングツリーは、グラフのすべての頂点を接続し、最小の合計エッジ重みを持つツリーです。
Kruskalのアルゴリズムは、 最小ウェイト （MSTにはまだない）を繰り返し選択し、そのエッジで接続された2つの頂点がMSTにまだ接続されていない場合は最終結果に追加します。 Union - データ構造を使用して、2つの頂点がすでにMSTに接続されているかどうかを確認できます。 MSTのいくつかのプロパティは次のとおりです。
-
n個の頂点を有するグラフのMSTは、厳密にn-1n辺を有する。 - 各頂点から他のすべての頂点までの固有のパスが存在します。
シンプルで詳細な実装
サイクル検出を効率的に処理するために、各ノードをツリーの一部として考える。エッジを追加するとき、2つのコンポーネントノードが別個のツリーの一部であるかどうかをチェックします。最初に、各ノードは1ノードのツリーを構成します。
algorithm kruskalMST'(G: a graph)
sort G's edges by their value
MST = a forest of trees, initially each tree is a node in the graph
for each edge e in G:
if the root of the tree that e.first belongs to is not the same
as the root of the tree that e.second belongs to:
connect one of the roots to the other, thus merging two trees
return MST, which now a single-tree forest
シンプルな、ディスジョイントセットベースの実装
上記のフォレスト方法論は、実際には分離されたデータ構造であり、3つの主な操作が必要です。
subalgo makeSet(v: a node):
v.parent = v <- make a new tree rooted at v
subalgo findSet(v: a node):
if v.parent == v:
return v
return findSet(v.parent)
subalgo unionSet(v, u: nodes):
vRoot = findSet(v)
uRoot = findSet(u)
uRoot.parent = vRoot
algorithm kruskalMST''(G: a graph):
sort G's edges by their value
for each node n in G:
makeSet(n)
for each edge e in G:
if findSet(e.first) != findSet(e.second):
unionSet(e.first, e.second)
この素朴な実装は、ディスジョイントセットデータ構造を管理するためのO(n log n)時間をもたらし、Kruskalアルゴリズム全体のO(m*n log n)時間につながります。
最適な、ディスジョイントセットベースの実装
シンプルかつ最適でないディスジョイントセットサブアルゴリズムを改善するために、次の2つのことができます。
パス圧縮ヒューリスティック ：
findSetは、2より大きい高さのツリーを処理する必要はありません。このようなツリーを繰り返し終えると、下位ノードをルートに直接リンクし、将来のトラバーサルを最適化できます。subalgo findSet(v: a node): if v.parent != v v.parent = findSet(v.parent) return v.parent高さベースマージヒューリスティック ：各ノードに対して、そのサブツリーの高さを格納します。マージするときは、背の高いツリーを小さなツリーの親にして、誰の高さも上げないようにします。
subalgo unionSet(u, v: nodes): vRoot = findSet(v) uRoot = findSet(u) if vRoot == uRoot: return if vRoot.height < uRoot.height: vRoot.parent = uRoot else if vRoot.height > uRoot.height: uRoot.parent = vRoot else: uRoot.parent = vRoot uRoot.height = uRoot.height + 1
これは各演算のO(alpha(n))時間につながります。 alphaは急成長するアッカーマン関数の逆数なので、非常に遅く成長し、実用上はO(1)と考えることができます。
これにより、最初のソートのため、KruskalのアルゴリズムO(m log m + m) = O(m log m)全体が作成されO(m log m + m) = O(m log m) 。
注意
パス圧縮はツリーの高さを減らすことがあります。したがって、結合操作中のツリーの高さを比較することは簡単な作業ではないかもしれません。したがって、ツリーの高さを格納して計算する複雑さを回避するために、結果の親をランダムに選択することができます。
subalgo unionSet(u, v: nodes):
vRoot = findSet(v)
uRoot = findSet(u)
if vRoot == uRoot:
return
if random() % 2 == 0:
vRoot.parent = uRoot
else:
uRoot.parent = vRoot
実際には、このランダム化されたアルゴリズムは、 findSet操作のためのパス圧縮と同等のパフォーマンスを実現しますが、実装ははるかに簡単です。
シンプルでハイレベルな実装
サイクルを作成しない場合は、エッジを値でソートし、ソート順にMSTに追加します。
algorithm kruskalMST(G: a graph)
sort G's edges by their value
MST = an empty graph
for each edge e in G:
if adding e to MST does not create a cycle:
add e to MST
return MST