Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in JavaScript

Depth First Traversal of Graph

Explore how to implement depth-first traversal of graphs using recursion in JavaScript. Understand graph structures, adjacency lists, and recursive traversal techniques to visit all nodes efficiently. This lesson helps you develop skills to solve graph-related problems in coding interviews.

We'll cover the following...

What is a Graph?

Graphs represent pairwise relationships between objects. A graph is typically represented as a set of edges and a set of nodes.

A node, also known as a vertex, is a fundamental part of a graph. It is the entity that has a name, known as the key, and other information related to that entity.

A relationship between nodes is expressed using edges.

An edge between two nodes expresses a one-way or two-way relationship between the nodes.

In a computer program, graphs are represented using an Adjacency List or an Adjacency Matrix. We will be using adjacency list representation for this course. If you want to study graphs in detail, review Interview Refresher Course on Data Structures in Javascript.

The diagram below shows an example graph. It has 66 nodes and 66 edges.

What does “Depth First Traversal of Graph” Mean?

The depth-first graph traversal involves visiting all nodes of the graph once depth-wise.

Starting from any node, we continue moving to the adjacent nodes until we reach the farthest level or the deepest node. We then move back to the starting point and select another adjacent node. We probe to the farthest level and move back. This process continues until all nodes are visited. The algorithm is as follows:

Depth-First-Traversal(vertex u)
  if (u is not visited) {
    // mark u as visited
    // print u
  }

  for (each adjacent vertex v) {
    helperFunction(v);
  }
  return;
}

Let’s take a look at the visual representation of the depth-first algorithm:

Implementation

Javascript (babel-node)
import Graph from './graph.js'
function helperFunction(myGraph, currentNode, visited) {
  // Mark the currentNode as visited and print it 
  if (visited[currentNode] == false) {
    visited[currentNode] = true
    console.log(currentNode)
  }
  if (myGraph.graph.has(currentNode) == true) {
    var currentAdjacencyList = myGraph.graph.get(currentNode)
    for (var i = 0; i < currentAdjacencyList.length; i++)
    {
      var temp = currentAdjacencyList[i];
      if (visited[temp] == false) {
        // Recur for all the vertices adjacent to currentNode
        helperFunction(myGraph, temp, visited)
      }
    } 
  }
}
function DFS(myGraph) {
  var visited = new Array(myGraph.vertices).fill(false); //Initially all vertices are marked as unvisited
  helperFunction(myGraph, 0, visited) // Call helper function starting from node 0
}
// Driver code 
// Create a graph given in the above diagram 
var myGraph = new Graph(6); 
myGraph.addEdge(0, 1); 
myGraph.addEdge(1, 2); 
myGraph.addEdge(1, 3); 
myGraph.addEdge(2, 4); 
myGraph.addEdge(3, 4); 
myGraph.addEdge(3, 5); 
console.log("DFS Graph Traversal")
DFS(myGraph)

Explanation

The starting vertex is included as a parameter to the DFS() function.

In the recursive implementation of Depth-First Traversal(in file index.js) we traverse as far as possible from each branch, backtracking once we have visited the last node of that branch.

In the above code, recursion takes place in the helperFunction().

Notice that the recursive case is easily detectable in the code. What will be the base case for this code?

Let’s dry run our code:

Now, it is your turn to try solving some problems.