Breadth-First Search

Finally, we will finish lesson 7 in the Algorithms Unplugged book which talks mainly about Depth-First Search. Still, the last part talks about Breadth-First Search which is a search technique that depends on searching a graph level by level until reaches the destination.

It’s not used for solving a maze because in a maze you can’t simply jump from one place to another unless they are a road between them.

In the case of searching your friend’s profile, you may find it with BFS faster than DFS because the target may not be too deep in the nodes of the tree and it’s located near the start of the graph.

So Breadth-First Search is very useful in such cases and an essential algorithm that you must know.

How to implement it ?

To implement BFS we need to use a queue which is a data structure in which the first come element is the first served element (FIFO). The queue will be used to store all the nodes of the same level in the tree.

function BFS(graph,start,goal){
  //queue store all elements to be searched in order
  const queue = [start]
  //contain all nodes that has been already searched
  const state = {}
  //loop until there no element to be searched in queue
  while(queue.length > 0){
    //first element is the current element to be searched
    const currentNode = queue.shift();
    //check the element not has been visited yet
    if(state[currentNode] !== "discovered"){
      //check if we have reach our goal
      if(currentNode === goal){
        return "Goal Found!"
      }
      //upate state of element to be visited
      state[currentNode] = "discovered"
      //loop through neighbours of element
      for(let neighbour of graph[currentNode]){
          if(state[neighbour] !== "discovered"){
             //push any neighbour that has not been visited
             queue.push(neighbour)
          }
      }
    }
  }
 return "Goal not found"
}

We have implemented the code and we will use the example that we have used with iterative DFS to make it clear how it works differently.

You have a friend who was with you at your university and you want to search for him on a social media app. but all you remember about him is his shape in such case you can ask simply any of your colleagues about his name I know but let’s consider you are too shy to ask anyone and want to depend on yourself.

Let’s say you have 4 friends: Gad, Rabeeh, Fero, and Dino. You search for Rami and you will start from Fero.

Considering an object which represents all your colleagues and their friend list as follows:

const friends ={
 Gad:["Rabeeh","Fero","Ali"],
 Dino:["Fero","Fadel"],
 Rabeeh:["Gad","Fero","Rami"],
 Fero:["Dino","Saeed"],
 Ali:["Gad"],
 Saeed:["Fero"],
 Fadel:["Dino"]
}

As you can see in the image below at first we had only one item in the queue which is Fero’s Page and it will marked as visited and shifted out of the queue.

Then we will push into the queue all the friends list of Fero’s page and the queue will become as shown below, in the second iteration Dino’s page will be marked as visited and it will be shifted from the queue.

All the friends list on Dino’s page will be pushed in the queue except any page that has been visited before like Fero’s page so we will push Fadel’s page only.

After that, we will go to Saeed’s page and we will mark it as visited shift it from the queue and add nothing to our queue because he has only Fero as a friend which has already been visited before.

We will go to Rabeeh’s page and push in our queue the friend list of Rabeeh which will be Gad and Rami. Gad has already been added but no problem to add him again because at first time we reach out to him he will be marked as visited and in second time we will not go to his page again as it’s already visited so we will shift it only and go to next page.

You can also use a set instead of an array to be your queue and that will guarantee no repeated elements are represented.

Anyway, let’s complete our example we will go to Gad’s profile page mark it as visited and push Ali’s page in the queue.

Going to Fadel’s page we will add nothing to our queue and shift Fadel then we will shift Gad from the queue without doing anything as he already has been visited.

After shifting Fadel and Gad from our array we will find our goal which is Rami’s page and our function returns “Goal Found!”

That’s how the Breadth-First search works and if you do the refactor that we have done in the Depth-First search which was searching in only your colleagues you will see That you will have fewer iterations because you will only add to the queue the unvisited pages, the pages of your colleagues and the goal itself.

The queue will be as follows only 4 (while loop) iterations which is less than six loops. it is not very much optimization but if you search a larger data it will be good to consider such a refactor.

This is how the queue will be through the process:

[Fero] → [Dino,Rabeeh,Gad] → [Rabeeh,Gad] → [Gad , Rami] → [Rami]

How to consider which algorithm to use when searching graph ?

Depth-first search is slightly easier to implement since you can do it using recursion without the need for any data structure. Further, the breadth-first search usually uses more memory for difficult problems.

On the other hand, breadth-first search always finds the shortest path (concerning the number of edges) and is fast, in particular when the graph is very large but the goal is too close to the start point. In this case, the depth-first search can easily get lost in far regions in the graph.

From all of these, we conclude that no algorithm is better than the other it depends on the case you are dealing with.

That’s it we have finished lesson 7 in the Algorithms unplugged book there are still 3 lessons to finish part 1 in the book.

The next lesson is Pledge’s Algorithm which makes it tougher and more challenging by enabling us to escape from a Dark Maze.