When exploring graphs in computer science, one of the most important algorithms you’ll come across is Breadth-First Search, or BFS for short. If you imagine a network of connected points—like friends on a social media platform, intersections on a map, or cities connected by roads—BFS is like exploring one level of connections at a time before moving deeper. It starts from a source node and visits all its neighbors first, then moves to the next level of neighbors, and so on.
with hands-on learning.
get the skills and confidence to land your next move.
BFS is extremely useful in many real-world applications. It’s used in finding the shortest path in unweighted graphs, building chat systems that detect who is connected to whom, and even solving puzzles like the Rubik’s Cube. It forms the foundation of several advanced algorithms in artificial intelligence, networking, and data science. In this article, we’ll learn how to implement BFS in Ruby in multiple ways—using loops, recursion, and queues—so beginners can easily understand how it works step-by-step.
Program 1: Simple BFS Using a Queue
This first program introduces the classic and most common implementation of BFS using a queue. It explores each node level by level starting from a given node.
def bfs(graph, start)
visited = {}
queue = [start]
while !queue.empty?
node = queue.shift
next if visited[node]
visited[node] = true
puts node
graph[node].each do |neighbor|
queue << neighbor unless visited[neighbor]
end
end
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
puts "Breadth-First Search starting from A:"
bfs(graph, 'A')In this version, the program uses a queue to keep track of which nodes to visit next. It starts from node A, visits all its direct neighbors B and C, and then moves to their neighbors. Each node is marked as visited to avoid repetition. This is the simplest and most widely used version of BFS because it’s efficient and easy to follow.
Program 2: BFS That Records the Order of Visit
Sometimes we want to keep track of the exact order in which nodes were visited. This version stores the visited order in an array.
def bfs_order(graph, start)
visited = {}
queue = [start]
order = []
while !queue.empty?
node = queue.shift
next if visited[node]
visited[node] = true
order << node
graph[node].each do |neighbor|
queue << neighbor unless visited[neighbor]
end
end
order
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
puts "BFS visit order: #{bfs_order(graph, 'A').join(' -> ')}"Here, instead of printing nodes one by one, the program collects them into an array and prints them in order after traversal. This approach is helpful when you want to process data after the entire BFS is complete, such as saving the visit order for analysis or debugging.
Program 3: BFS Using Adjacency Matrix
In some problems, the graph is given as an adjacency matrix rather than a hash. This program shows how BFS can work in that situation.
def bfs_matrix(matrix, start)
visited = Array.new(matrix.size, false)
queue = [start]
while !queue.empty?
node = queue.shift
next if visited[node]
visited[node] = true
puts "Visited node #{node}"
matrix[node].each_with_index do |connected, i|
queue << i if connected == 1 && !visited[i]
end
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 "BFS using adjacency matrix (start node 0):"
bfs_matrix(matrix, 0)In this example, the graph is represented as a two-dimensional array. Each 1 means there’s a connection between two nodes. BFS works exactly the same as before—it visits all connected nodes level by level. This version is useful when the input graph comes from files, grids, or numeric datasets.
Program 4: BFS to Find Shortest Path in an Unweighted Graph
Breadth-First Search can also be used to find the shortest path between two nodes when edges have equal weight or no weight.
def bfs_shortest_path(graph, start, goal)
visited = { start => true }
queue = [[start]]
while !queue.empty?
path = queue.shift
node = path.last
return path if node == goal
graph[node].each do |neighbor|
next if visited[neighbor]
visited[neighbor] = true
new_path = path + [neighbor]
queue << new_path
end
end
nil
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
path = bfs_shortest_path(graph, 'A', 'F')
puts "Shortest path from A to F: #{path ? path.join(' -> ') : 'No path found'}"Here, BFS keeps track of the entire path while traversing. Once the goal node is found, it immediately returns the full path. This method ensures the shortest route is found because BFS explores level by level. It’s a great example of how BFS differs from DFS—while DFS dives deep, BFS stays shallow and finds the shortest route first.
Program 5: BFS Using Recursion
While BFS is naturally iterative, it can still be implemented recursively by calling a helper function for each level of nodes.
def bfs_recursive(graph, queue, visited)
return if queue.empty?
node = queue.shift
return if visited[node]
visited[node] = true
puts node
graph[node].each do |neighbor|
queue << neighbor unless visited[neighbor]
end
bfs_recursive(graph, queue, visited)
end
graph = {
'A' => ['B', 'C'],
'B' => ['D', 'E'],
'C' => ['F'],
'D' => [],
'E' => ['F'],
'F' => []
}
puts "Recursive BFS starting from A:"
bfs_recursive(graph, ['A'], {})Although recursion is more commonly used with DFS, this recursive BFS version helps beginners understand how queue management works level by level. It demonstrates that recursion can be used creatively even for algorithms that are not naturally recursive.
Program 6: BFS for Connected Components
Graphs are not always connected; sometimes there are separate clusters of nodes. BFS can help find and print each connected component individually.
def bfs_connected(graph)
visited = {}
graph.keys.each do |node|
next if visited[node]
queue = [node]
puts "\nComponent:"
while !queue.empty?
current = queue.shift
next if visited[current]
visited[current] = true
print "#{current} "
graph[current].each do |neighbor|
queue << neighbor unless visited[neighbor]
end
end
end
end
graph = {
'A' => ['B'],
'B' => ['A'],
'C' => ['D'],
'D' => ['C'],
'E' => []
}
puts "BFS for connected components:"
bfs_connected(graph)This version explores each disconnected section of the graph separately. It prints all the nodes that belong to the same connected component together. For example, in social networks, this technique helps identify isolated groups of users.
Frequently Asked Questions (FAQ)
This section covers common questions that beginners often have about implementing Breadth-First Search in Ruby.
Q1. What is Breadth-First Search in simple words?
Breadth-First Search (BFS) is a way of exploring a graph level by level, starting from one node and visiting all its direct neighbors before moving to their neighbors.
Q2. How is BFS different from DFS?
BFS explores in layers (or breadth), while DFS goes deep into one branch before backtracking. BFS uses a queue, whereas DFS uses a stack or recursion.
Q3. Where is BFS used in real life?
It’s used in network routing, social media friend suggestions, shortest path problems, and puzzle-solving algorithms.
Q4. Can BFS be used for weighted graphs?
BFS is ideal for unweighted graphs. For weighted graphs, algorithms like Dijkstra’s or A* Search are better suited.
Q5. Why do we use a queue in BFS?
The queue helps keep track of which node to visit next, ensuring that nodes are explored in the correct order—from closest to farthest.
Conclusion
Breadth-First Search is one of the simplest and most powerful graph traversal algorithms every programmer should learn. In Ruby, implementing BFS is both straightforward and rewarding because the language’s clean syntax makes it easy to focus on the logic itself. Whether you’re using it to find paths, explore connected components, or understand the basics of graph theory, BFS lays the foundation for more advanced algorithms.
Keep experimenting with these Ruby BFS programs—change the graphs, try different starting points, or combine BFS with DFS to solve more complex problems. The more you practice, the more natural these algorithms will feel, and soon, you’ll be using them confidently in real projects.
