# 인접 행렬로 구현된 그래프를 참조한다
require 'graph'

# 너비 우선 탐색에서 큐를 참조한다
require 'circular_queue'

class Graph
  # 깊이 우선 탐색
  def depth_first_search( start_vertex_name = nil )
    unless start_vertex_name == nil
      start_index = find_vertex(start_vertex_name)
    else
      start_index = 0
    end

    if @max_vertex_number < 0 || start_index < 0
      puts
      return
    end

    visited = []

    (0..@max_vertex_number).each {|i| visited[i] = false}

    depth_first_search_recursive(visited, start_index)

    puts
  end

  # 너비 우선 탐색
  def breadth_first_search( start_vertex_name = nil )
    unless start_vertex_name == nil
      start_index = find_vertex(start_vertex_name)
    else
      start_index = 0
    end

    if @max_vertex_number < 0 || start_index < 0
      puts
      return
    end

    visited = []

    (0..@max_vertex_number).each {|i| visited[i] = false}

    queue = CircularQueue.new(@max_vertex_number + 1)

    current_visit = start_index

    visited[current_visit] = true
    print "-> " + @vertex_set[current_visit].to_s

    loop do
      (0..@adjacent_matrix[current_visit].length).each do |i|
        if 1 == @adjacent_matrix[current_visit][i] && false == visited[i]

          visited[i] = true
          print "-> " + @vertex_set[i].to_s
          
          queue.enqueue(i)
          
        end

      end

      break if true == queue.is_empty

      current_visit = queue.dequeue
      
    end

    puts

  end

  private
  # 스택 부분을 재귀 구조가 알아서 처리하므로 따로 스택을 push / pop 할 필요 없음
  def depth_first_search_recursive(visited_list, current_visit)
    visited_list[current_visit] = true
    print "-> " + @vertex_set[current_visit].to_s

    (0..@adjacent_matrix[current_visit].length).each do |i|

      if 1 == @adjacent_matrix[current_visit][i] && false == visited_list[i]
        depth_first_search_recursive(visited_list, i)
      end

    end

    # 방문하지 않은 정점이 없다면 스택을 pop 하여 구한 가장 마지막 방문 정점을
    # v로 설정하고 다시 (2) 를 수행한다

  end


end

graph = Graph.new(false)

graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')
graph.add_vertex('E')
graph.add_vertex('F')
graph.add_vertex('G')

graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'E')
graph.add_edge('D', 'G')
graph.add_edge('E', 'G')
graph.add_edge('F', 'G')

puts "깊이 우선 탐색(BFS) >> "
graph.depth_first_search
puts
puts "너비 우선 탐색(DFS) >> "
graph.breadth_first_search