Depth-first-search

Now that we’ve gone through the breadth-first-search, we’ll move on to the depth-first-search algorithm. Depth-first-search utilizes a stack data structure, where you can only use .push() and .pop() to add and remove the items. It is an edge based technique whereas the breadth-first-search is vertex. Depth-first-search is more suitable for applications for games and puzzles. It starts at the root node and instead moving by levels horizontally as the breadth-first-search, it moves top to bottom laterally. The biggest asset depth-first-search provides is that it is lower in memory requirements.

DFS(node) {
   // Create a Stack and add our initial node in it
   let s = new Stack(this.nodes.length);
   let explored = new Set();
   s.push(node);

   // Mark the first node as explored
   explored.add(node);

   // We'll continue till our Stack gets empty
   while (!s.isEmpty()) {
      let t = s.pop();

   // Log every element that comes out of the Stack
      console.log(t);

   // 1. In the edges object, we search for nodes this node is directly connected to.
   // 2. We filter out the nodes that have already been explored.
   // 3. Then we mark each unexplored node as explored and push it to the Stack.
   this.edges[t]
   .filter(n => !explored.has(n))
   .forEach(n => {
      explored.add(n);
      s.push(n);
      });
   }
}