クラスカルのアルゴリズム

昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。

アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。

二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。

今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下のグラフです。

このグラフで最小全域木を構成すると、コストの総和は 37 になります。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class DisjointSet:
    def __init__ (self, size):
        self.parent = [0] * size
        self.rank =   [0] * size
        for i in xrange(size):
            self.parent[i] = i

    def union(self, x, y):
        self.link( self.find_set(x), self.find_set(y) )
            
    def link (self, x, y):
        if self.rank[x] > self.rank[y]:
            self.parent[y] = self.parent[x]
        else:
            self.parent[x] = self.parent[y]
            if (self.rank[x] == self.rank[y]):
                self.rank[x] += self.rank[y] + 1

    def find_set (self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find_set(self.parent[x])
        return self.parent[x]

class Edge:
    def __init__(self, src, dst, weight):
        self.src   = src
        self.dst   = dst
        self.weight = weight

edges = [
    Edge('a', 'b', 4),
    Edge('a', 'h', 8),
    Edge('b', 'c', 8),
    Edge('b', 'h', 11),
    Edge('c', 'd', 7),
    Edge('c', 'f', 4),
    Edge('c', 'i', 2),
    Edge('d', 'f', 14),
    Edge('d', 'e', 9),
    Edge('e', 'f', 10),
    Edge('f', 'g', 2),
    Edge('g', 'h', 1),
    Edge('g', 'i', 6),
    Edge('h', 'i', 7),
    ]

c2i = { 'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6, 'h':7, 'i':8 }
set = DisjointSet(9) # the number of vertices
mst = []

edges.sort(lambda x, y: x.weight - y.weight )
for x in edges:
    u = c2i[x.src]
    v = c2i[x.dst]
    if set.find_set(u) != set.find_set(v):
        mst.append(x)
        set.union(u, v)

print sum(map(lambda x: x.weight, mst))

実際に実行してみると

% python mst_kluskal.py
37

となり、正しく動いているようです。

クラスカルのアルゴリズムのポイントは二つあります。ひとつめは、コストが最小の辺から順番に見ていってその場その場で最善のもの (閉路にならない) を選ぶ、という貪欲戦略を採るところです。

二つ目は着目中の辺が「閉路にならない辺」かどうかを判定する方法です。これにはその辺の両端点が同じ木に属しているかどうかを調べます。属していれば閉路となってしまうので、最小全域木の辺には加えません。この、着目中の同じ木に属しているかどうかを調べるのに Disjoint Set (互いに疎な集合のためのデータ構造) を利用するところが味噌です。Disjoint Set を利用すると、ある集合の代表元同士を比較したり、二つの疎な集合を結合することが可能です。いずれも実装を工夫すると現実的かつ高速な計算量で実現できます。

なぜこのような手順で最小全域木が構成できるかより詳しくは参考文献や id:tksmd さんによる神資料 (SlideShare) を参照してください。

二つのポイントのうち前者は、重みで予めソートしておいて先頭から順番に見ていけば良いだけです。後者のために、ソースコードでは Disjoint Set を実装しています。Python には組み込みで set クラスがありますが、ここでは学習のため Disjoint Set を自前で実装しました。

クラスカルのアルゴリズムは実装してみると比較的単純です。中核の処理は Disjoint Set の操作であり適切なデータ構造を選ぶことがいかに大切であるかが改めてよく分かります。

参考文献

[1] の第 23 章が今回のテーマです。計算量の評価や貪欲戦略の正当性の証明などは [1] に詳細な解説があります。[2] にもクラスカル、プリムのアルゴリズム共に解説があり、わかりやすかったです。

2009.6.14 追記

diff --git a/mst_kluskal.py b/mst_kluskal.py
index 16feab6..6220c28 100644
--- a/mst_kluskal.py
+++ b/mst_kluskal.py
@@ -48,7 +48,7 @@ edges = [
     ]

 c2i = { 'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6, 'h':7, 'i':8 }
-set = DisjointSet(len(edges))
+set = DisjointSet(9) # the number of vertices
 mst = []

 edges.sort(lambda x, y: x.weight - y.weight )

Disjoint Set が内部で持つ配列の大きさの指定を辺の数にしていたのを、頂点の数に修正。(id:rahaema さんありがとうございます)