Depth First Traversal

It is an algorithm that let you explore a tree or a graph. This algorithm explores the depth of the tree or a graph as deep as possible along one branch before backtracking and exploring other branches. Depth First Traversal uses stack to keep track of the nodes that are next to be visited.

Implementation

Steps

• Start at a certain node
• Mark it as visited
• Move to one of the unvisited neighbours
• Repeat until you cannot go any deeper
• Backtrack and explore other paths

Code Example

function depthFirstTraversalGraph(graph: Record<string, string[]>, start: string): void {  
  const stack = [start];  
  const visited = new Set<string>();  
  
  while (queue.length > 0) {  
    const node = queue.pop()!;  
      
    if (!visited.has(node)) {  
      console.log(node);  
      visited.add(node);  
        
      for (const neighbor of graph[node]) {  
        if (!visited.has(neighbor)) {  
          stack.push(neighbor);  
        }  
      }  
    }  
  }  
}  
  
const graph = {  
  A: ['B', 'C'],  
  B: ['A', 'D'],  
  C: ['A', 'D'],  
  D: ['B', 'C'],  
};