Class: UnionFind

Inherits:
Object
  • Object
show all
Defined in:
lib/MinimumSpanningTree.rb

Overview

Implementação da estrutura de dados Union-Find

Instance Method Summary collapse

Constructor Details

#initialize(size) ⇒ UnionFind

Returns a new instance of UnionFind.



3
4
5
 
# File 'lib/MinimumSpanningTree.rb', line 3

def initialize(size)
  @parent = Array.new(size, -1)
end

Instance Method Details

#find(x) ⇒ Object 



7
8
9
10
11
12
13
14
15
16
 
# File 'lib/MinimumSpanningTree.rb', line 7

def find(x)
  x_root = x
  x_root = @parent[x_root] while @parent[x_root] >= 0
  while x != x_root
    new_parent = @parent[x]
    @parent[x] = x_root
    x = new_parent
  end
  x_root
end

#union(x, y) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/MinimumSpanningTree.rb', line 18

def union(x, y)
  x_root = find(x)
  y_root = find(y)
  return if x_root == y_root

  if @parent[x_root] <= @parent[y_root]
    @parent[x_root] += @parent[y_root]
    @parent[y_root] = x_root
  else
    @parent[y_root] += @parent[x_root]
    @parent[x_root] = y_root
  end
end