Depth first search(DFS) using Javascript

Depth first search simply says that once you have visited a vertex, start exploring its child nodes and sub child nodes until there is no node to explore for that vertex and then move to next vertex.

Exploring each child and its children and moving to another node and repeat the process

Depth first search is also known as Pre order traversal.

Once you have visited new vertex, suspend the exploration of current vertex and start exploring new vertex.

Stack is the data structure used for this traversal.

Let’s take an example of below tree and try to understand the working of depth first search. we’ll start exploring the tree from node 1.

First we’ll start from 1 and explore 2, then we explore 5 and then 9. Once we have explored all the children of 2, we’ll come back to 3. Then from 3, we’ll visit 6 and then 10 and once we explore 10 we’ll come back to 3 and explore 7, Once we visit all the vertex of 3, we’ll move to 4 and visit 8. In this way, we’ll explore all the vertex in a pre order traversal method.

Sudo code for depth first approach:

- start from the root element(it can be any)
- push the root in stack.
- Explore its child. (check if visited or not)
- if not visited, push to stack, and repeat the process until we explore all the 
vertices.
- if all nodes are processed, get value from stack and check for vertices that are not visited.

Let’s understand the working for this undirected graph:

The adjacency matrix for this graph will be:

In our problem, we’ll use DFS approach to get visit all the nodes and find the distance from the root element to all the nodes.

First, let’s create a function to check if any unvisited vertex exist for our current vertex .

/**
 * Function to check if any unvisited neighour vertex exist for current vertex
 * @param {*} currentNode , current node(vertex) that is being processed
 * @param {*} graph , graph, the adjacency matrix representation
 * @param {*} visitedNodes , Hashmap for vertex that are already been visited
 * @returns
 */
const findUnVisitedNode = (currentNode, graph, visitedNodes) => {
  const currentConnectedNodes = graph[currentNode]; //current connected vertex for this current vertex
  let neighborIdx = -1; // making it initial to -1, as no vertex is unvisited
  currentConnectedNodes.forEach((element, idx) => {
    // finding the first neighour unvisited vertex
    if (element == 1 && !visitedNodes[idx] && neighborIdx == -1) {
      neighborIdx = idx;
    }
  });
  return neighborIdx;
};

Now, let’s create our algorithm to visit all vertex and calculate distance between them.

/**
 * Traversing through the graph
 * @param {Array} graph , graph matrix
 * @param {Number} rootNode , root node to start from
 */
const dfs = (graph, rootNode) => {
  // storing distance to the root node
  let nodeDistance = {};
  // start all distance from infinity
  for (let i = 0; i < graph.length; i++) {
    nodeDistance[i] = Infinity;
  }

  // distance from root node to root node is 0
  nodeDistance[rootNode] = 0;

  // creating a stack to keep track of nodes to visit later
  let stack = [rootNode];

  // setting the current vertex as visited as we don;t want to create a loop around it
  let visitedNodes = { [rootNode]: true };

  // iterate while we have vertex in stack
  while (stack.length) {
    // taking the current value in the stack that needs to be processed
    const currentNode = stack.pop();
    // checking if unvisited nodes are there or not
    const unvisitedNode = findUnVisitedNode(currentNode, graph, visitedNodes);
    // checking is any unvisited vertex exist for this current vertex or not
    if (unvisitedNode >= 0) {
      if (!visitedNodes[unvisitedNode]) {
        // value is not set as per now
        if (nodeDistance[unvisitedNode] == Infinity)
          nodeDistance[unvisitedNode] = nodeDistance[currentNode] + 1;
        visitedNodes[unvisitedNode] = true;
        // if a vertex is unvisited then we need to push the current vertex as well
        // as the next vertex that we need to explore
        stack.push(...[currentNode, unvisitedNode]);
      }
    } else {
      // if all vertices are visited then we don;t have to add any value in stack
      visitedNodes[unvisitedNode] = true;
    }
  }

  return nodeDistance;
};

let’s call our function to perform

const newdfsGraph = [
  [0, 1, 1, 0, 0],
  [1, 0, 0, 1, 0],
  [1, 0, 0, 1, 1],
  [0, 1, 1, 0, 0],
  [0, 0, 1, 0, 0],
];

console.log(dfs(newdfsGraph, 1));

DFS explore the depth of one vertex first and then move on to next vertex.

Stay tuned for more to come, If you are new here, do checkout our Algorithms with Javascript blog, we are covering few of the most commonly used algorithms.

In the next blog, we’ll go through Dijkstra’s algorithms ( Single source path finding).