The world’s leading publication for data science, AI, and ML professionals.

Top Coding Algorithms – Breadth First Search

Let's directly get into the topic.

Pseudo Code

procedure BFS(G, start_v) is
      let Q be a queue
      label start_v as discovered
      Q.enqueue(start_v)
      while Q is not empty do
          v := Q.dequeue()
          if v is the goal then
              return v
          for all edges from v to w in G.adjacentEdges(v) do
             if w is not labeled as discovered then
                 label w as discovered
                 w.parent := v
                 Q.enqueue(w)

The implementation of Breadth First Search uses queue and while loop comparing to its cousin of depth first search uses recursion, and remember this, I believe, can help you at least build the structure during your coding interview.

Implementation

Consider the most basic task:

To find all the paths from 0 to 6.

Notice the bidirectional arrow of 1 and 4, which means if we don’t track the visited node during search, the path would go backward.

A few points need to take notice here:

  • Notice the queue contains 2 elements, current node and current path. Based on the problem you meet, it could be depth or other things.
  • The queue.pop(0) ensures that we always consider the first element in the queue, which makes it breadth first.
  • If we hit a leave node with no children, then we continue to the next
if curr_node not in self.graph.keys():                
     continue
  • The if child not in curr_path checks if we are going backward, which avoids to visit a node twice.
  • Makes sure to curr_path.copy() , otherwise paths of different children would be entangled.

Coding Questions

Let’s see how we can apply it flexibly.

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

    3
   / 
  9  20
    /  
   15   7

return its minimum depth = 2. (This is a question from leetcode)

The major changes here is that our path is replaced by depth as the question required.

Now the question comes, what if we want the maximum depth? Go have a try.


Related Articles