BFS & DFS

Because Graphs are non-linear, you cannot simply loop from i = 0 to N to visit all nodes. We must use traversal algorithms to systematically visit every vertex exactly once.

To prevent infinite loops in cyclic graphs, both algorithms require a visited Hash Set to keep track of nodes we have already seen.

1. Breadth-First Search (BFS)

BFS explores the graph level by level, expanding outwards like ripples in a pond. It visits all immediate neighbors of a node before moving on to the neighbors' neighbors.

BFS strictly uses a Queue (FIFO).

Real-World Uses

• Shortest Path on Unweighted Graphs: BFS guarantees that the first time you reach the destination node, you have found the absolute shortest path (fewest number of edges).
• Social Networks: Finding friends of friends (e.g., "3rd degree connection" on LinkedIn).

Colors represent levels: Root -> Neighbors (Level 1) -> Neighbors of Neighbors (Level 2)

Implementation

function bfs(graph: Map<string, string[]>, startNode: string): void {
  const queue: string[] = [startNode];
  const visited: Set<string> = new Set([startNode]);
  
  while (queue.length > 0) {
    const current = queue.shift()!; // Dequeue
    console.log(`Visited: ${current}`);
    
    const neighbors = graph.get(current) || [];
    
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // Mark as visited immediately upon enqueueing!
        queue.push(neighbor);
      }
    }
  }
}

2. Depth-First Search (DFS)

DFS dives as deep as possible down a single path until it hits a dead end. Once it hits a dead end, it backtracks to the previous node and explores the next unvisited branch.

DFS strictly uses a Stack (LIFO). Usually, we don't manually create a stack array; we just use the Call Stack via Recursion.

Real-World Uses

• Solving Mazes / Puzzles: Finding any path to the exit.
• Topological Sorting: Resolving build dependencies.
• Cycle Detection: Checking if an undirected graph contains a loop.

Implementation

function dfsRecursive(graph: Map<string, string[]>, current: string, visited: Set<string>): void {
  // Base case / Mark visited
  visited.add(current);
  console.log(`Visited: ${current}`);
  
  const neighbors = graph.get(current) || [];
  
  // Recursively explore all unvisited neighbors
  for (const neighbor of neighbors) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited);
    }
  }
}

// Initial call
// const visited = new Set<string>();
// dfsRecursive(graph, "A", visited);

Iterative DFS Implementation

If the graph is massive, recursion will cause a Stack Overflow. You can easily convert DFS to be iterative by manually using an array as a Stack.

function dfsIterative(graph: Map<string, string[]>, startNode: string): void {
  const stack: string[] = [startNode];
  const visited: Set<string> = new Set();
  
  while (stack.length > 0) {
    const current = stack.pop()!; // Pop from top of stack
    
    if (!visited.has(current)) {
      visited.add(current);
      console.log(`Visited: ${current}`);
      
      const neighbors = graph.get(current) || [];
      // Push unvisited neighbors onto the stack
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

Time and Space Complexity

For both BFS and DFS, the time and space complexity are identical (assuming an Adjacency List representation).

• Time Complexity: $O(V + E)$ (where V is Vertices and E is Edges). We visit every node once, and iterate through every edge once.
• Space Complexity: $O(V)$ for the visited Set and the Queue/Stack.