GraphStore/bfs.rb at master · rralev/GraphStore · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Bfs
  def initialize(graph)
    @graph = graph
    @used = {}
    @pred = {}
  end

  def compute(vertex)
    queue = Queue.new
    queue << vertex
    @used[vertex] = 1
    @pred[vertex] = vertex
    list = []

    while queue.size > 0 do
      front = queue.pop
      list << front

      @graph[front].each { |v|
        if @used[v] == nil
          queue << v
          @used[v] = 1
          @pred[v] = front
        end
      } if @graph[front] != nil
    end

    list
  end

  def get_path_between_two_vertices(u, v)
    compute(u)
    list = []

    vertex = v
    while vertex != @pred[vertex] do
      list << vertex
      vertex = @pred[vertex]
    end
    list << vertex

    list.reverse
  end
end