Breadth-first search is an algorithm for finding (or traversing) graph data structures. You start at the root and explore the branch as wide as possible before going back (also called backtracking).

Let’s consider the next graph:

GraphGraph

While finding I, algorithm will start with A and go as wide as possible and go to the next node:

A
B C
D E
F G H
I

BFS written in Ruby:

class Node

  attr_reader :key
  attr_accessor :children

  def initialize(key)
    @key = key
    @children = []
  end

end

def bfs(root, target)
  queue = [root]
  until queue.empty?

    # remove the first node from the queue
    current = queue.shift
    # check if this node has the right key (and return if so)
    if current.key == target
      return current
    end
    # add this node's children to the queue
    queue = queue + current.children
  end
   # We finished the until loop (went through all nodes)
  # without finding the node we wanted.
  # implicitly return nil
  nil
end

root = Node.new('A')
b = Node.new('B')
c = Node.new('C')
d = Node.new('D')
e = Node.new('E')
f = Node.new('F')
g = Node.new('G')
h = Node.new('H')
i = Node.new('I')

root.children << b
root.children << c
b.children << d
b.children << e
e.children << f
e.children << g
e.children << h
f.children << i

puts "\n### searching C"
p bfs(root, 'C')
#=> #<Node:0x007fb8aa114cb0 @key="C", @children=[]>

puts "\n### searching I"
p bfs(root, 'I')
#=> #<Node:0x007fb8aa114968 @key="I", @children=[]>