はむ吉(のんびり)の練習ノート

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

Prim法とKruskal法をPython 3で実装してみた:無向グラフの最小全域木を求めるアルゴリズム

ふと思い立ち、Prim(プリム)法とKruskal(クラスカル)法をPython 3で実装しました。これらは無向グラフの最小全域木を求めるアルゴリズムであり、競技プログラミングでも用いられることがあるようです。この記事では、学習の記録を兼ねて、最小全域木や上記の手法の概略について述べてから、これらのアルゴリズムPython 3による実装例を、Minimum Spanning Tree | Aizu Online Judgeの答案として示します。

無向グラフの最小全域木とそれを求めるアルゴリズム

連結である*1無向グラフG全域木(spanning tree)は、Gの部分グラフであって、Gのすべての頂点を含む木を指します*2Gの全域木であって、それが含む辺の重みの合計が最小になるものを、G最小全域木(minimum spanning tree)と呼びます*3。なお、最小全域木は無向グラフだけではなく有向グラフについても考えることができます*4が、この記事では無向グラフの最小全域木のみを扱うことにします。

Prim法Kruskal法は、重み付き無向グラフの最小全域木を求めるためのアルゴリズムです*5。Prim法は、ある頂点vだけからなる木Tを考え、これとほかの頂点を結ぶ重みが最小の辺をTに付け加えることを貪欲法のごとく繰り返すことで、最小全域木を構成するアルゴリズムです*6。以下に示すような、優先度付きキュー(二分ヒープ)と隣接リストを用いた実装では、計算量がO(|E|\log |V|)となります*7。これに対して、Kruskal法では、重みの小さい順に辺を見ていき、閉路や多重辺がなければTに辺を追加するという方法をとります*8。閉路や多重辺の有無はUnion-Find木を用いて行えます。このときに、計算量はO(|E|\log|V|)となります*9

連結である重み付き無向グラフおよびその最小全域木と、Prim法やKruskal法の関係を下に図示します。なお、このグラフはMinimum Spanning Tree | Aizu Online Judgeの入力例に基づきます。
f:id:hamukichi_nbr:20160330165845p:plain

Python 3による実装例

Prim法の実装例

以下にMinimum Spanning Tree | Aizu Online Judgeに対するPrim法による解答コードを示します。Prim法の実装は『アルゴリズムクイックリファレンス』p.188を参考にして行いました。Python標準ライブラリのheapqを用いてリストを優先度付きキュー(二分ヒープ)として用いています。

Kraskal法の実装例

続いてKraskal法によるものを示します。Union-FindはB: Union Find - AtCoder Typical Contest 001 | AtCoderを参考にして実装しました。それ以外は『プログラミングコンテストチャレンジブック』(第2版)に基づきました。

感想

グラフやそれを扱うアルゴリズムを学んでいくうちに、解ける問題の幅が広がってきた気がします。グラフに限らず、いろいろなアルゴリズムを今後も少しずつ学んでいきたいところです。それと同時に、問題演習を通じて実装力や考察力といったものもつけたいと思っています。

*1:連結ではないグラフには全域木が存在しません。ただし、全域を考えることはできます(参考:wikipedia:en:Spanning_Tree)。

*2:参考:wikipedia:en:Spanning_Tree

*3:参考:wikipedia:en:Minimum_Spanning_Tree

*4:参考:最小全域木問題 - 情報科学と人工知能のノート

*5:重みがない場合には、幅優先探索最小全域木を求めることができます。

*6:参考:『プログラミングコンテストチャレンジブック』(第2版)p.100

*7:参考:wikipedia:en:Prim's algorithm

*8:参考:『プログラミングコンテストチャレンジブック』(第2版)p.101

*9:参考:前掲書p.101