Applying Breadth First Search algorithm to solve problem with two dimensions array
Sun 26 Jan 2020

Breadth First Search

If you have not known Breadth First Search yet: https://en.wikipedia.org/wiki/Breadth-first_search This is a traditional algorithms we should know cause it would be an efficient tool to solve complex problem, especially related to tree. If we are dealing with tree we have to know how to traverse a tree. This is a way to do that along with Depth First Search that we will introduce in another article.

Now we have a tree like following:

We have a tree including 5 nodes. Like it said, we traverse tree in breadth dimension. Thus, it should be A -> B -> C -> D -> E - The same level. In order to do that we have to use a Queue.

Why we use Queue? First In First Out, we ensure that we always start traversing a level with first node of this level and ending with last node of this level. We can see the explanation in above picture.

  1. Enqueue A.
  2. Dequeue A, take it out to find its children.
  3. Enqueue A's children (next level). So A at level 0, now this queue contains nodes at level 1: [B, C]. A is starting node and C is ending node. With Queue we ensure that that next node to be dequeued is B and C then.
  4. Dequeue B to find its children. We get [C, D, E].
  5. Dequeue C we get [D, E] because C does not have children so no need to enqueue. [D, E] now is same level (breadth).
  6. Repeat 1-5 that is Breadth First Search.

If you are using Ruby to solve problem. This is Queue implementation for ruby using array to prove FIFO characteristic.

class Queue
  attr_reader :data

  def initialize(data)
    @data = data || []
  end

  def enqueue(el)
    @data.push(el)
  end

  def dequeue
    @data.shift
  end

  def empty?
    data.empty?
  end
end

Those are sufficient to solve following problem.

Finding words appears in two dimension array.

# Input:
# [ 
# ["E", "E", "X", "B", "C"],
# ["E", "E", "X", "B", "A"],
# ["L", "A", "F", "O", "B"],
# ["M", "D", "O", "G", "T"]
# ]
# dictionary = ['HELLO', 'CAT', 'DOG', 'FOOBAR', 'CAB']
# 
# Output: The words in dictionary appear in two dimension array with one condition:
# each letters in same word connect each other (next to another). For example:
# "D" next to "O". "O" next to "G" => DOG appears in array. Same way, CAB also appears in array.

Approach

  1. We can see that it is two dimension array. What make us think of BFS? That is letters connect each other. So with "CAT" if we have a queue like this [C, A, T] - They are next to each other. That means C first, A second and last T. If T appears in queue that means we traversed to last letter of "CAT". Thus "CAT" is valid.
  2. Next problem is how can we make a queue like that. Relying on "connect each other". We take first letter of "CAT" first. Then we find next "A" to enqueue. If next "A" exists once "A" enqueued, the next step to dequeued would be "A". This algorithm repeats until:
    • queue is empty => invalid.
    • last letter "T" found => valid.

We broke it down into two smaller problems (1) and (2) above. This is Problem Solving Approach - Simplify problem. If we can't solve current problem, let's break it down to smaller ones until we can solve them easily.

Solve problem

This is my implementation for (1) and (2).

def exists?(word, arr, positions)
  found = false

  queue = Queue.new(positions[word[0]].dup)
  while(!queue.empty?) do
    current_position = queue.dequeue
    row, column = current_position
    up       = [row - 1, column]
    down     = [row + 1, column]
    left     = [row, column - 1]
    right    = [row, column + 1]

    idx = word.index(arr[row][column])

    if arr[row][column] == word[word.size-1]
      found = true
      break
    end

    next_position = positions[word[idx+1]]
    next if next_position.nil?

    queue.enqueue(up)    if next_position.include?(up)
    queue.enqueue(down)  if next_position.include?(down)
    queue.enqueue(left)  if next_position.include?(left)
    queue.enqueue(right) if next_position.include?(right)
  end
  found
end

positions is a data structure containing position of a letter, for example: { C: [[1,2], [3,4], [5,6]] } We can easily find this by looping array.


Thanks for reading!