Depth-First Search (DFS) Part 2

In yesterday's story, I explained how to make a depth-first search recursively but sometimes you want to avoid recursive one reason being that at each recursive call in the computer implementation, additional time is spent to allocate variables.

So you may need to implement it in an iterative way the iterative way has more lines of code but it can be more clear than recursion for some people.

Let’s start doing it with the same graph we had before this time we will have to use a data structure to help us do iteratively which is stack.

Stack is a data structure that works with LIFO (last input first output) so we will use it to store our map it’s considered as the ball of thread that Ariadne gives to Athenian to help him find the monster faster and turn back to her.

The stack will always have on the top of it the next road we will go through and we will pop out from it any road that has been already visited or has no more roads to visit.

Every road will have its name: road name, mode: will be either forward in case the first time to choose it or backward in case you have already been there and return to see other roads that you can take and the number of exits: which determine the number of times you exit certain road and go through one of its neighbours and it also determine the current neighbour index.

This is how to implement it:

function iterativeDFS(start, goal, graph) {
  let stack = [{ road: start, mode: 'forwards', exits: 0 }];
  let visited = new Set();

  while (stack.length > 0) {
    let { road, mode, exits } = stack[stack.length - 1];
    // Check new 
    if (mode === 'forwards') {
      // Check if road is already visited
      if (visited.has(road)) {
        stack.pop();
        continue;
      }
      // add new road to visited roads
      visited.add(road);
      // check new road has neighbors
      let neighbors = graph[road];
      // pop out new road with old mode
      stack.pop();
      if (!neighbors || neighbors.length === 0) {
        // No neighbors you reach a dead road
        continue;
      }
      // push new road with it's new mode
      stack.push({ road, mode: 'backwards', exits: 0 });
      
    } else {
      // Coming back
      let neighbors = graph[road]; //check current road neighbours
      //check if we hadn't finish all the neighbours
      if (exits < neighbors.length) { 
        // reach the goal
        if (neighbors[exits] === goal) {
          return 'Goal found!';
        }
        //increase number of exits
        stack[stack.length - 1].exits++;
        //push new road
        stack.push({ road: neighbors[exits], mode: 'forwards', exits: 0 });
      } else {
        // No more unexplored roads
        stack.pop();
      }
    }
  }
  return 'Goal not found!';
}

// Example usage
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F', 'G'],
  D: ['B'],
  E: ['B', 'H'],
  F: ['C'],
  G: ['C', 'I'],
  H: ['E'],
  I: ['G'],
};

const startJunction = 'A';
const goalJunction = 'I';

const result = iterativeDFS(startJunction, goalJunction, graph);
console.log(result); // output: Goal Found!

When you run this code you will see it has a less renders than recursive because when you reach the goal you exit the function. Doing it recursively will return you to the root you started from by default but doing it in this way you will reach your goal only if you try to print out the stack you will see it has its way back to your start point so you aren’t get lost at anyway.

So let’s go now to an example and see how the above code will execute it, 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.

In such case, you will go through all the accounts of your colleagues and you will see if any of them has the one you search for in his friend list. Let’s say you have 4 friends: Gad, Rabeeh, Fero, and Dino. You search for Rami.

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"]
}

In such a case, you can refactor the code to search only colleagues because it’s very difficult to find Rami in Ali’s friend list. After all, Ali is not even in your university so you can search faster by doing such a thing.

This is the new implementation of the code that we will go through:

function iterativeDFS(start, goal, friendsList, mutualFriends) {
 let history = [{ friendName: start, mode: 'forwards', exits: 0 }];
 let visitedPages = new Set();
 
 while (history.length > 0) {
   let { friendName, mode, exits } = history[history.length - 1];
   // Check New friend
   if (mode === 'forwards') {
     // Check if friend page is already visited
     if (visitedPages.has(friendName)) {
     history.pop();
     continue;
   }
   // add new page to visited pages
   visitedPages.add(friendName);
   // check new page has friends list
   let friends = friendsList[friendName];
   // pop out new friend page with old mode
   history.pop();
   if (!friends || friends.length === 0) {
   // No neighbors you reach a dead page
   continue;
   }
   // push new friend page with it's new mode
   history.push({ friendName, mode: 'backwards', exits: 0 });
   }
   else {
     // Coming back
     let friends = friendsList[friendName]; //check current friend list for friend
     //check if we hadn't finish all the friend list
     if (exits < friends.length) { 
       //increase number of exits
       history[history.length - 1].exits++;
       if(friends[exits] === goal){
         return "Goal Found!"
       }
     if(mutualFriends.findIndex(friend=> friend=== friends[exits]) === -1 ){
       continue
     }
     //push new friend page
     history.push({friendName: friends[exits], mode: 'forwards', exits: 0 });
   } else {
     // No more friends in friend list
     history.pop();
     }
   }
 }
 return 'Goal not found!';
}

// Example usage
const friends ={
 Gad:["Rabeeh","Fero","Ali"],
 Dino:["Fero","Fadel"],
 Rabeeh:["Gad","Fero","Rami"],
 Fero:["Dino","Saeed","Rabeeh","Gad"],
 Ali:["Gad"],
 Saeed:["Fero"],
 Fadel:["Dino"]
}
const colleguesFriends = ["Gad","Rabeeh","Fero","Dino"]
const result = iterativeDFS("Fero", "Rami", friends, colleguesFriends);
console.log(result); // output: Goal Found!

As you can see in the image above when you start you will go from Fero’s page to Dino’s page and you will see he has 2 friends (Fero, Fadel). Fero’s page has already been visited and Fadel is not among your colleagues so you will return to Fero.

When returning to Fero you will find that Saeed is not a colleague so you will move to Rabeeh's Page and see his friend list. We went to Gad’s Page and found that Rabeeh’s page has already been visited so you will go to the next one in the list which is Fero you have already visited him and we will see the next one which is Ali not one of our colleagues.

So we returned to Rabeeh’s page and found that Gad and Fero had already been visited and hooray we found the image of that guy his name is Rami let’s send him a friend request.

And That’s it we have seen life examples of how to do a Depth-first search and implement it iteratively.

There is a last part of this lesson that I will explain tomorrow which is contrary to depth-first search and called breadth-first search so stay tuned for more lessons simply explained from the Algorithms Unplugged book.