Depth-First Search (DFS)

class Graph
  def initialize
    @adjacency_list = {}
  end
  
  def add_vertex(vertex)
    @adjacency_list[vertex] ||= []
  end
  
  def add_edge(vertex1, vertex2)
    add_vertex(vertex1)
    add_vertex(vertex2)
    
    @adjacency_list[vertex1] << vertex2
    @adjacency_list[vertex2] << vertex1
  end
  
  def dfs(start_vertex, visited = Set.new, result = [])
    return result if visited.include?(start_vertex)
    
    visited.add(start_vertex)
    result << start_vertex
    
    @adjacency_list[start_vertex]&.each do |neighbor|
      dfs(neighbor, visited, result) unless visited.include?(neighbor)
    end
    
    result
  end
  
  def dfs_iterative(start_vertex)
    visited = Set.new
    stack = [start_vertex]
    result = []
    
    while !stack.empty?
      vertex = stack.pop
      
      unless visited.include?(vertex)
        visited.add(vertex)
        result << vertex
        
        @adjacency_list[vertex]&.reverse_each do |neighbor|
          stack.push(neighbor) unless visited.include?(neighbor)
        end
      end
    end
    
    result
  end
end

# Example usage
graph = Graph.new
%w[A B C D E F].each { |vertex| graph.add_vertex(vertex) }

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

puts "DFS Recursive: #{graph.dfs('A')}"
puts "DFS Iterative: #{graph.dfs_iterative('A')}"