Breath First Traversal

It is an algorithm that lets you explore a tree of a graph. This algorithm explores all the nodes at the present depth level before moving on to nodes at the next depth level. Breath First Traversal uses queues to track nodes that need to be visited next.

Implementation

Steps

• Start at the root or arbitrary node
• Visit the node and add all neighbours to the queue
• Dequeue the node and enqueue neighbours
• Repeat until the queue is empty

Code Example

function breadthFirstTraversalGraph(graph: Record<string, string[]>, start: string): void {  
  const queue = [start]; // Queue to track the nodes to visit  
  const visited = new Set<string>(); // Set to track visited nodes  
  
  while (queue.length > 0) {  
    const node = queue.shift()!; // Dequeue the first node from the queue  
      
    if (!visited.has(node)) {  
      console.log(node); // Visit the node  
      visited.add(node); // Mark the node as visited  
        
      // Enqueue all unvisited neighbors  
      for (const neighbor of graph[node]) {  
        if (!visited.has(neighbor)) {  
          queue.push(neighbor);  
        }  
      }  
    }  
  }  
}  
  
// Example graph  
const graph = {  
  A: ['B', 'C'],  
  B: ['A', 'D'],  
  C: ['A', 'D'],  
  D: ['B', 'C'],  
};  
  
// Perform BFS starting from node 'A'  
breadthFirstTraversalGraph(graph, 'A');  
// Output: A, B, C, D