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

id:naoyaさんが，クラスカルのアルゴリズムをPythonで実装されています。

• http://d.hatena.ne.jp/naoya/20090610/1244647082

自分の理解を深めるために，Rubyで書いてみました。

mst_kluskal.rb

#!/usr/bin/env ruby

class DisjointSet
  attr_accessor :parent, :rank
  def initialize(size)
    @parent = Array.new(size, 0)
    @rank   = Array.new(size, 0)
    for i in 0...size
      @parent[i] = i
    end
  end

  def union(x, y)
    self.link(self.find_set(x), self.find_set(y))
  end

  def link(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
      end
    end
  end

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

class Edge
  attr_reader :src, :dst, :weight
  def initialize(src, dst, weight)
    @src = src
    @dst = dst
    @weight = weight
  end
end

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

c2i = { 'a' => 0, 'b' => 1, 'c' => 2, 'd' => 3, 'e' => 4,
        'f' => 5, 'g' => 6, 'h' => 7, 'i' => 8}
set = DisjointSet.new(c2i.size)
mst = []

# edges.sort!{ |a, b| a.weight <=> b.weight }
edges = edges.sort_by{ |a| a.weight }
edges.each do |x|
  u = c2i[x.src]
  v = c2i[x.dst]
  if set.find_set(u) != set.find_set(v)
    mst << x
    set.union(u, v)
  end
end

puts mst.inject(0){ |result, item| result + item.weight }

実行結果

$ ./mst_kluskal.rb
37

ちょっとした疑問点(1)

Array#sort!メソッドは，破壊的にソートを行うことができますが，要素の比較回数が気になるので，sort_byメソッドを使った方が効率が良いと聞いたことがあります。上記でもsort_byメソッドを使ったのですが，これには，破壊的にレシーバを変更するsort_by!はないんですね?

ちょっとした疑問点(2)

id:naoya さんは，配列parentとrankの大きさをエッジの数で確保していますが，ノードの数だけでいいような気がするのですが…。

6/15追記

ノードの数でいいようです。id:naoya さんも修正されています。

6/20追記

id:tksmd さんがPythonでプリムのアルゴリズムを書かれています。参考にさせてもらって，いつかRubyで書いてみたいと思います。
http://d.hatena.ne.jp/tksmd/20090616#p1