When learning about graph algorithms, one of the first and most fascinating ones you’ll encounter is Depth-First Search, often called DFS. This algorithm explores a graph by going as deep as possible along one branch before backtracking. It’s like exploring a maze — you follow one path until you can’t go any further, then return and try another route. DFS is one of the simplest yet most powerful algorithms used in computer science.
with hands-on learning.
get the skills and confidence to land your next move.
Depth-First Search is commonly used in many areas, such as solving puzzles, detecting cycles in a graph, scheduling problems, pathfinding, and even in AI for decision-making. It helps programmers explore relationships and connections between elements efficiently. In this article, we’ll learn how to implement DFS in Ruby in multiple ways — using recursion, stacks, loops, and other techniques. Whether you are new to Ruby or brushing up on algorithms, this step-by-step explanation will make it easy to follow along.
Program 1: Simple Recursive Depth-First Search in Ruby
This is the most common and elegant way to implement DFS. It uses recursion to visit nodes, exploring each branch deeply before returning.
def dfs(graph, start, visited = {})
return if visited[start]
visited[start] = true
puts start
graph[start].each do |neighbor|
dfs(graph, neighbor, visited)
end
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
puts "Depth-First Search starting from A:"
dfs(graph, 'A')This program defines a graph using a Ruby hash and performs a DFS starting from node ‘A’. It prints each visited node in the order it is explored. The recursive nature of this solution makes it clean and easy to understand — the function simply calls itself until all connected nodes are visited. For beginners, this approach helps to grasp how recursion naturally mirrors the DFS concept.
Program 2: Depth-First Search Using a Stack (Iterative Approach)
Recursion is elegant, but sometimes we want more control or need to avoid stack overflow for very large graphs. This version uses an explicit stack to handle the traversal manually.
def dfs_iterative(graph, start)
visited = {}
stack = [start]
while !stack.empty?
node = stack.pop
next if visited[node]
visited[node] = true
puts node
graph[node].reverse.each do |neighbor|
stack.push(neighbor)
end
end
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
puts "Iterative DFS starting from A:"
dfs_iterative(graph, 'A')Here, we use a stack (an array in Ruby) to track the nodes to visit. Each time, we pop a node, print it, and push its neighbors. Reversing the neighbors ensures the traversal order matches the recursive version. This approach helps beginners see that recursion is not magic — it’s just a stack handled automatically by the system.
Program 3: DFS with Adjacency Matrix Representation
Graphs can also be stored as matrices instead of hashes. This program demonstrates how DFS works when data is stored differently.
def dfs_matrix(matrix, start, visited = [])
visited[start] = true
puts "Visited node #{start}"
matrix[start].each_with_index do |connected, i|
dfs_matrix(matrix, i, visited) if connected == 1 && !visited[i]
end
end
matrix = [
[0, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0]
]
puts "DFS using adjacency matrix (start node 0):"
dfs_matrix(matrix, 0, [])Instead of using node names like ‘A’ or ‘B’, this program uses numeric indices. The adjacency matrix holds 1 where connections exist. DFS works the same way — visiting connected nodes recursively until all are explored. This version is useful for understanding how graphs are represented internally in algorithms and computer memory.
Program 4: DFS with Node Discovery and Finishing Times
In this version, we’ll track when we discover and finish exploring each node — a common concept in algorithm theory.
def dfs_with_times(graph, start, visited = {}, time = {count: 0}, discover = {}, finish = {})
visited[start] = true
time[:count] += 1
discover[start] = time[:count]
puts "Discovered #{start} at time #{discover[start]}"
graph[start].each do |neighbor|
dfs_with_times(graph, neighbor, visited, time, discover, finish) unless visited[neighbor]
end
time[:count] += 1
finish[start] = time[:count]
puts "Finished #{start} at time #{finish[start]}"
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
puts "DFS with discovery and finish times:"
dfs_with_times(graph, 'A')This version shows the exact order in which nodes are discovered and finished. It helps you visualize the depth and backtracking nature of DFS. It’s very helpful for advanced learning, such as topological sorting and detecting cycles.
Program 5: DFS for Connected Components
Sometimes a graph isn’t fully connected. DFS can help find all connected components, which are separate clusters of nodes.
def dfs_connected(graph, node, visited)
return if visited[node]
visited[node] = true
print "#{node} "
graph[node].each { |n| dfs_connected(graph, n, visited) }
end
def find_components(graph)
visited = {}
graph.keys.each do |node|
next if visited[node]
puts "\nComponent:"
dfs_connected(graph, node, visited)
end
end
graph = {
'A' => ['B'],
'B' => ['A'],
'C' => ['D'],
'D' => ['C'],
'E' => []
}
puts "DFS for connected components:"
find_components(graph)This program identifies different groups of connected nodes. When run, it prints out each component separately. Beginners can use this to understand how DFS can explore isolated parts of a graph without missing any nodes.
Program 6: DFS Path Finder Between Two Nodes
Finally, let’s build a simple DFS program to find a path between two nodes in a graph.
def dfs_path(graph, start, goal, visited = {}, path = [])
visited[start] = true
path << start
return path.dup if start == goal
graph[start].each do |neighbor|
next if visited[neighbor]
result = dfs_path(graph, neighbor, goal, visited, path)
return result if result && result.last == goal
end
path.pop
nil
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
path = dfs_path(graph, 'A', 'F')
puts "Path from A to F: #{path ? path.join(' -> ') : 'No path found'}"This example searches for a path between two nodes. It keeps track of the path as it explores and returns once the goal is found. This is a practical example showing how DFS can be used in pathfinding problems, like navigating maps or solving puzzles.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about implementing DFS in Ruby.
Q1. What is Depth-First Search in simple words?
Depth-First Search is a way to explore all the nodes or points in a graph by going as deep as possible along one route before coming back and exploring others.
Q2. What is the difference between DFS and BFS?
DFS explores deep into a branch before moving to another, while BFS (Breadth-First Search) explores all neighbors first before moving deeper.
Q3. Is recursion the only way to do DFS?
No, recursion is just one way. You can also use a stack manually, which gives more control and avoids deep recursive calls.
Q4. Where is DFS used in real life?
It’s used in web crawling, solving mazes, analyzing social networks, game AI, and many other computer applications.
Q5. Can DFS detect cycles in a graph?
Yes, by marking visited nodes and checking if a node is revisited before the recursion finishes, you can detect cycles using DFS.
Conclusion
Depth-First Search is one of those fundamental algorithms every programmer should understand. In Ruby, it’s beautifully simple to implement, and through recursion or iteration, it teaches important lessons about problem-solving and graph exploration. By practicing the different methods we covered — recursive, iterative, matrix-based, and even path-finding — you can build a strong foundation in algorithmic thinking.
Keep experimenting with different graphs, modify the code, and try to visualize how DFS works step by step. The more you explore, the deeper your understanding will grow — just like the algorithm itself!
