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 = 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 }