Imagine you're standing in the middle of a massive city subway system. You have a map, but it's not a traditional map; it's just a list of stations and the tunnels that connect them. In computer science, that's a Graph. Unlike a Tree—which we've looked at before and has a strict parent-child hierarchy—a Graph is a bit more chaotic. It's just a collection of nodes (stations) and edges (the tunnels connecting them). There's no "root" here; you can start anywhere and potentially end up back where you started.

To get this into Ruby, we need to map these real-world concepts to data structures:

• The Station becomes a vertex (or node). In our code, this will just be a key in a Hash.
• The Tunnel becomes an edge. This is represented by the value in our Hash—an array of all the other stations that specific station connects to.
• The Map itself is an adjacency list. I prefer this over an adjacency matrix because, in most real-world scenarios, every station isn't connected to every other station, and a Hash keeps our memory usage lean.

Building the Adjacency List

Let's start by sketching out a basic Graph class. I'm going to use a Hash where the keys are the vertices and the values are arrays of neighbors. It's the most idiomatic way to handle this in Ruby.

class Graph
  def initialize
    @adjacency_list = {}
  end

  def add_vertex(vertex)
    @adjacency_list[vertex] = [] unless @adjacency_list.key?(vertex)
  end

  def add_edge(v1, v2)
    add_vertex(v1)
    add_vertex(v2)
    @adjacency_list[v1] << v2
    @adjacency_list[v2] << v1 # Assuming an undirected graph
  end

  def neighbors(vertex)
    @adjacency_list[vertex] || []
  end
end

Notice how add_edge calls add_vertex. I do this so you don't have to manually register every single single node before creating a connection. It just makes the API feel smoother.

Rippling Outward with BFS

Breadth-First Search (BFS) is like dropping a pebble in a pond. The ripple hits everything one step away, then everything two steps away, and so on. If you're trying to find the shortest path between two subway stations, BFS is your best friend because it explores all immediate neighbors before moving deeper.

To implement this, we need a Queue. We visit a node, mark it as seen, and then toss all its unvisited neighbors into the queue to be processed later.

def bfs(start_node)
  visited = Set.new
  queue = [start_node]
  visited.add(start_node)

  while queue.any?
    current = queue.shift # Remove from the front
    puts "Visiting #{current}"

    neighbors(current).each do |neighbor|
      unless visited.include?(neighbor)
        visited.add(neighbor)
        queue << neighbor # Add to the back
      end
    end
  end
end

I used a Set for visited because looking up an item in a Set is O(1), whereas an Array would be O(n). When your graph grows to thousands of nodes, that difference is the gap between a snappy app and a frozen one.

Going Deep with DFS

Depth-First Search (DFS) is a different beast. Instead of rippling outward, DFS is like an explorer who picks one tunnel and follows it as far as it possibly goes until they hit a dead end. Only then do they backtrack to the last junction and try a different path. This is incredibly useful for things like solving mazes or detecting cycles in a dependency graph.

The cleanest way to write DFS in Ruby is via recursion. The call stack effectively acts as our "memory" of where we've been.

def dfs(vertex, visited = Set.new)
  visited.add(vertex)
  puts "Visiting #{vertex}"

  neighbors(vertex).each do |neighbor|
    dfs(neighbor, visited) unless visited.include?(neighbor)
  end
  
  visited
end

One thing to keep in mind: because DFS uses recursion, you can hit a SystemStackError if your graph is absurdly deep (thousands of levels). If you're dealing with massive datasets, you'd want to implement this using an explicit Stack (an array with pop) instead of recursion, but for most cases, the recursive approach is much more readable.

📋 Practical Task

Build a Course Prerequisite Dependency Checker

You need to build a tool for a university that determines if a student can take a specific course based on its prerequisites. Since prerequisites form a directed graph (Course A $\rightarrow$ Course B), you'll need to modify the Graph implementation from the lesson.

Requirements:

• Create a CourseGraph class.
• Implement add_prerequisite(course, prerequisite). This should be a directed edge (the prerequisite leads to the course, not vice-versa).
• Implement a method can_take?(student_completed_courses, target_course).
  • This method should use DFS to find all the prerequisites (and the prerequisites of those prerequisites) required for the target_course.
  • Return true if every course in that dependency chain exists in the student_completed_courses list.
  • Return false otherwise.

Test Case:

graph = CourseGraph.new
graph.add_prerequisite("CS102", "CS101")
graph.add_prerequisite("CS201", "CS102")
graph.add_prerequisite("CS301", "CS201")

completed = ["CS101", "CS102"]
puts graph.can_take?(completed, "CS201") # Should be true
puts graph.can_take?(completed, "CS301") # Should be false (needs CS201)