Simple Explanation on BFS and DFS Graph Traversal Methods

Graph Traversal is one of the most important topics in the Graph series. It is also one of the most popular interview questions one might expect, because of the ton of real-world applications there are! As discussed in the last blog, we understood different methods of adding and removing edges and vertex.

In this blog we will discuss methods that we can employ in order to search, visit or update each vertex in a graph, their implementation with JavaScript, time complexity, and differences.

Why Graph Traversal Methods are Important?

Before moving forward with the article, one may ask why should we care. So here are some real-world applications which are based on the graph traversal method we extensively use,

• Peer to Peer networking
• Web Crawlers
• Suggesting movies or video matches/recommendations
• GPS navigation
• Finding the shortest path between two points

Also read, Simple Explanation on Sorting Algorithms with JavaScript | Part 1

Problems with Graph Traversal

When we talk about Graph traversal methods, it generally means the process of visiting, checking, or updating each node but in real-world applications where the number of nodes can be in thousands or millions, it may not be very practical. In actual practice, we generally try to find the nearest neighbors or the most similar node or shortest path from one vertex to another.

If we look into a Tree data structure, which is a special subset of a Graph, if we try to reach any specific node placed anywhere in the tree, we have only one special node that we know we can start looking from, which is known as Root node whereas, in Graph, we don’t have any such node.

During Graph traversal you may visit a node that you have already traversed and as the graph becomes denser, time complexities increase. In order to solve it, when we traverse each vertex, we either marked it a color or visitation, so that even though the node appears again during the traverse, it is ignored and the path is not further pursued.

Also read, Learning to Think Like a Computer

Types of Graph Traversal Methods

To solve the above problems we use two most popular tree-based algorithms to traverse methods:-

1. Breadth-first search
2. Depth-first search

Depth First Search (DFS)

Depth First Search is a tree-based traversing algorithm. In the DFS algorithm, we try to visit child vertices before visiting the sibling vertices of the current vertex. In other words, in DFS we are prioritizing visiting children of the current vertex before we visit its sibling vertices or you can say, we deepen the traversal before widening.

Implementation of Depth First Search method using JS

Recursive Method

• Create a function and name it as depthFirstSearch which accepts one argument, a starting node.
• Create a list to store the end result, to be returned at the end.
• Create an object to store all the visited vertices so that we don’t have to visit them again.
• Create a helper function and name it as dfs which accepts a vertex,
  • The helper function should return early if the given vertex is empty
  • The helper function should put the given vertex in the visited object, and then push that vertex into the result array.
  • Loop over all the values of the adjcencyList for that vertex
  • If any of the values have not been visited (added in visited object), then recursively invoke the helper function with that vertex.
• Invoke the helper function with the starting vertex
• Return the final array.

Pseudocode

DFS(vertex):
    if vertex is empty:
  	return (this is our base case)
  add vertex to result list
  mark vertex as visited
  for each neighbour in vertex's neighbors:
  	if neighbor is not viisted:
    	recursively calls DFS on neighbor

Code Snippet

function dfs(vertex) {
  if (!vertex) {
    return null;
  }
  visisted[vertex] = true;
  result.push(vertex);
  adjacencyList[vertex].forEach((neighbor) => {
    if (!visisted[neighbor]) {
      return dfs(neighbor);
    }
  });
}

function depthFirstSearch(start) {
  const result = [];
  const visited = {};
  const adjacencyList = this.aadjacencyList;
  dfs(start);

  return result;
}

Also read, What is Big O Notation – Space and Time Complexity

Iterative Method

• Create a function and name it as depthFirstSearch which accepts one argument, a starting node.
• Create a stack to help users keep track of vertices.
• Create a list to store the end result, to be returned at the end.
• Create an object to store all the visited vertices so that we don’t have to visit them again.
• Add the starting vertex to the stack and mark it visited.
• While the stack has something in it,
  • Pop the next vertex from the stack
  • If that vertex hasn’t been visited yet then,
    • Mark it as visited
    • Add it to the result list
    • Push all of its neighbors into the stack
• And then finally return the result array

Pseudocode

DFS(start):
  let s be a stack
  s.push(start)
  while s is not empty
    vertex = s.pop
    if vertex is not labeled as discovered:
    	visit vertex (add to result list)
      lable vertex as discovered
      for each of vertex's neighbor, N do
      	s.push(N)

Code Snippet

function depthFirstSearch(start) {
  const stack = [start];
  const result = [];
  const visited = {};
  let currentVertex;

  visited[start] = true;
  while (stack.length) {
    currentVertex = stack.pop();
    result.push(currentVertex);
    this.adjacencyList[currentVertex].forEach((neighbor) => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        stack.push(neighbor);
      }
    });
  }
}

Also read, Simple Explanation of Tree traversal Operations with JavaScript

Breadth First Search (BFS)

Breadth First Search is also a tree-based traversing algorithm. In the BFS algorithm, we try to visit sibling vertices before seeing the child vertices of the current vertex. In other words, in BFS we are prioritizing seeing siblings of the current vertex before we visit its children’s vertices or you can say, we widen the traversal before deepening.

Note – BFS is implemented using a Queue data structure that traverses level by level, thus it is not easy to implement BFS through recursion but in DFS we use a Stack data structure to maintain a frontier, and recursion uses (or utilizes) a stack to maintain, well, the ‘call stack’. So implementing DFS using recursion simply means we are replacing stack with call stack but BFS does not use a stack, there is nothing we can replace with the call stack, and thus BFS implementation using recursion is hard.

Implementation of Breadth First Search method using JS

Iterative Method

• Create a function and name it as breadthFirstSearch which accepts one argument, a starting node.
• Create a queue and place the starting vertex in it.
• Create a list to store the end result, to be returned at the end.
• Create an object to store all the visited vertices so that we don’t have to visit them again.
• Mark the starting vertex as visited.
• Keep looping as long as the queue has some vertex inside it,
• Remove the first vertex and push it into the array which stores all the vertex that is already visited.
• If it is not inside the object that stores node visited, mark it as visited and enqueue that vertex.
• Once the loop is over, return the array of visited nodes.

Pseudocode

BFS(start):
  let start in queue
  
  while(queue is not empty)
  	vertex = queue.shift
    visit vertex (add to result list)
    if vertex is not labeled as discovered:
    		lable vertex as discovered
        add vertex to queue

Also read, Understanding Array, String, and Object Data Structure with JavaScript

Code Snippet

function breadthFirstSearch(start) {
  const queue = [start];
  const result = [];
  const visited = {};
  let currentVertex;

  while (queue.length) {
    currentVertex = queue.shift();
    result.push(currentVertex);

    this.adjacencyList[currentVertex].forEach((neighbor) => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }

  return result;
}

Also read, Basic operations in Graph Data structure

Difference between BFS and DFS

Like everything, both traversal methods come with their own pros and cons, so here is the list of differences between BFS and DFS:-

Also read, Introduction to Graph Data Structure

Final Words

BFS and DFS are the most important topics while preparing for interviews, it might look overwhelming at first, but with practice, you will surely be able to master them.

I hope you like the article, please comment and share with your friends and bookmark this website, and also do check our detailed articles on Data structure, Javascript, and programming.