Exploring Graphs with DFS and BFS in Ruby

Ahoy, brave Ruby developer! Join us on a nautical adventure as we sail through the high seas of graph traversal algorithms. Prepare to dive deep with Depth First Search (DFS) and chart a course across the breadth with Breadth First Search (BFS). Ready to hoist the sails and explore these algorithms in Ruby?

Depth First Search (DFS)

DFS explores a graph or tree like a deep-sea diver, plunging into the depths to uncover hidden treasures. It navigates as far as possible before resurfacing and exploring another branch. DFS uses a stack to keep track of its discoveries.

Implementing DFS in Ruby

Embark on a deep-sea exploration with this Ruby example, using a recursive DFS algorithm:

class UnderwaterCave
  attr_accessor :name, :item, :connected_caves

  def initialize(name, item)
    @name = name
    @item = item
    @connected_caves = []
  end
end

def depth_first_search(cave, treasure, visited = Set.new)
  return if visited.include?(cave)
  visited << cave

  return cave if cave.item == treasure

  cave.connected_caves.each do |neighboring_cave|
    result = depth_first_search(neighboring_cave, treasure, visited)
    return result if result
  end

  nil
end

# Example usage
start_cave = UnderwaterCave.new('1st', 'Sunken Ship')
cave2 = UnderwaterCave.new('2nd', 'Coral Reef')
cave3 = UnderwaterCave.new('3rd', 'Abyss')
cave4 = UnderwaterCave.new('4th', 'Treasure Chest')

start_cave.connected_caves.push(*[cave2, cave3])
cave2.connected_caves.push(*[cave4])

treasure_location = depth_first_search(start_cave, 'Treasure Chest')
puts "The #{treasure_location.item} was found in the #{treasure_location.name} cave!" if treasure_location

In this deep-sea adventure, we’re looking for a sunken treasure chest. We navigate through an underwater cave system to find it. Our algorithm uses DFS to explore the caves, marking each visited one on our treasure map.

Breadth First Search (BFS)

BFS navigates a graph or tree like a fleet of ships patrolling coastal waters, moving methodically across the breadth of the sea. It visits all neighbors of a node before proceeding to the next layer. BFS uses a queue to chart its course.

Implementing BFS in Ruby

Set sail with this Ruby example, implementing a BFS algorithm:

class Island
  attr_accessor :name, :neighboring_islands, :treasure

  def initialize(name, treasure=false)
    @name = name
    @treasure = treasure
    @neighboring_islands = []
  end
end

def breadth_first_search(start_island)
  queue = [start_island]
  visited = Set.new

  while !queue.empty?
    current = queue.shift
    next if visited.include?(current)
    visited << current

    return current if current.treasure

    queue.push(*current.neighboring_islands)
  end

  nil
end

# Example usage
start_island = Island.new('Mainland')
island2 = Island.new('Coral Isle')
island3 = Island.new('Pirate Cove')
island4 = Island.new('Treasure Island', true)

start_island.neighboring_islands.push(*[island2, island3])
island3.neighboring_islands.push(*[island4])

treasure_island = breadth_first_search(start_island)
puts "We found the treasure on #{treasure_island.name}!" if treasure_island

In this seafaring tale, we’re searching for a legendary treasure island. We explore a series of neighboring islands using BFS, plotting a course through the islands on our map as we go.

Comparing DFS and BFS

DFS and BFS are both graph traversal algorithms, but they have different approaches and applications. Let’s take a closer look at the differences and when to use each algorithm.

DFS: Depth First Search

DFS explores a graph by diving deep into a single branch before backtracking to explore the next one. It works by following one branch as far as possible, marking the visited nodes along the way, and then retracing its steps to explore other branches.

DFS is generally faster when exploring a deep tree or graph, where the target node is closer to the leaves. This algorithm excels at searching for a solution when the search space is vast, and it’s unclear how deep the solution might be. DFS is also space-efficient, requiring less memory than BFS.

BFS: Breadth First Search

BFS explores a graph layer by layer, visiting all nodes at the current depth before moving to the next level. It works by examining all neighbors of a node before moving deeper into the graph.

BFS is more suitable for searching wide, shallow trees or graphs, where the target node is closer to the root. This algorithm excels at finding the shortest path in a graph since it explores all nodes at the current depth before moving deeper. BFS requires more memory than DFS, as it keeps track of all nodes at the current level in a queue.

When to Use DFS or BFS

• Use DFS when:

  • You need to explore as deeply as possible.
  • The graph is significantly deeper than it is wide.
  • Memory is a concern, as DFS is more space-efficient.

• Use BFS when:

  • You need to find the shortest path.
  • The graph is significantly wider than it is deep.
  • Memory is not a significant concern.

In summary, DFS dives deep into a single branch before backtracking, while BFS explores all branches at the current level before descending deeper. Choose DFS when exploring deep trees or graphs and BFS when searching for the shortest path in wide, shallow trees or graphs.

Wrapping Up

Whether you’re a deep-sea explorer diving into the depths with DFS or a fleet admiral charting the breadth with BFS, these Ruby examples will guide you through the waves of graph traversal. DFS plunges into the depths, navigating as deep as possible, while BFS patrols the breadth, visiting all neighbors before moving deeper.

Set sail with these nautical-themed algorithms and let your Ruby programming skills soar like the wind in your sails. May you always find fair winds and following seas on your coding journey!