Breadth-First and Depth-First Search in JavaScript

When working with data structures like trees or graphs, two fundamental traversal techniques come in handy: Breadth-First Search (BFS) and Depth-First Search (DFS). These algorithms allow you to explore data from different angles, depending on the problem you’re solving. Whether you’re working on pathfinding, tree manipulation, or hierarchical data, understanding BFS and DFS will elevate your JavaScript coding skills.

In this post, we’ll walk through what these traversal methods are, how to implement them in JavaScript, and when to use each one with practical examples. By the end, you’ll feel confident applying BFS and DFS to real-world problems.

What is Breadth-First Search (BFS)?

Breadth-First Search (BFS) is an algorithm used to explore nodes level by level, starting from the root. In other words, BFS traverses the breadth (or width) of the tree or graph before diving deeper into its levels. BFS is ideal when you’re looking for the shortest path in unweighted graphs or when you need to explore all possibilities from the top level downwards.

How BFS Works:

BFS starts from a specific node, often called the root, and explores all its neighboring nodes.
It then moves to the neighbors of these nodes, and the process continues level by level.
This traversal is typically implemented using a queue data structure because BFS is inherently a First-In-First-Out (FIFO) process.

BFS Algorithm (in Steps):

Enqueue the starting node.
Dequeue a node from the queue and explore its neighbors.
For each neighbor, if it hasn’t been visited, mark it as visited and enqueue it.
Repeat until the queue is empty.

BFS Example in JavaScript:

Let’s start by applying BFS to traverse a simple graph.

function bfs(graph, startNode) {
  let queue = [startNode];
  let visited = new Set();

  while (queue.length > 0) {
    let node = queue.shift();
    if (!visited.has(node)) {
      console.log(node); // Process node
      visited.add(node);
      queue.push(...graph[node]); // Enqueue all neighbors
    }
  }
}

// Sample graph
const graph = {
  1: [2, 3],
  2: [4, 5],
  3: [6],
  4: [],
  5: [],
  6: []
};

// Traverse starting from node 1
bfs(graph, 1);

In this example, BFS starts at node 1, visits nodes 2 and 3 next, and continues to their children, nodes 4, 5, and 6.

Real-World Applications of BFS:

Shortest Path in Unweighted Graphs: BFS is used to find the shortest path between two nodes in an unweighted graph, like navigating a maze.
Level-Order Traversal of Trees: BFS is useful for level-order traversal of trees, where you want to process nodes level by level.

What is Depth-First Search (DFS)?

Depth-First Search (DFS), on the other hand, explores as deep as possible along each branch before backtracking. It traverses down a path as far as it can before moving to the next branch. DFS can be implemented using recursion (inherently using a stack), or iteratively using an explicit stack.

How DFS Works:

DFS starts at a root node and explores a path as deeply as possible before backtracking.
Once all paths from one node are explored, DFS moves to the next unexplored node.
DFS is usually implemented with a stack data structure (either explicitly or using recursion).

DFS Algorithm (in Steps):

Push the starting node onto the stack.
Pop a node from the stack and explore its neighbors.
For each neighbor, if it hasn’t been visited, mark it as visited and push it onto the stack.
Repeat until the stack is empty.

DFS Example in JavaScript:

Let’s implement DFS to traverse a graph.

function dfs(graph, startNode) {
  let stack = [startNode];
  let visited = new Set();

  while (stack.length > 0) {
    let node = stack.pop();
    if (!visited.has(node)) {
      console.log(node); // Process node
      visited.add(node);
      stack.push(...graph[node]); // Push all neighbors
    }
  }
}

// Traverse starting from node 1
dfs(graph, 1);

Here, DFS explores a path deeply before backtracking, following nodes 1 → 3 → 6, then backtracking to explore the remaining nodes.

Real-World Applications of DFS:

Maze Solving: DFS is used in algorithms to solve mazes, exploring paths as deeply as possible.
Topological Sorting: DFS helps in finding topological sorts in directed acyclic graphs (DAGs).
Pathfinding in Games: DFS can be used in certain types of pathfinding or search scenarios in game development.

BFS vs. DFS: When to Use Each?

Now that we know how both algorithms work, let’s discuss when you might prefer one over the other.

BFS:

Use when you need to find the shortest path: BFS excels at finding the shortest path in unweighted graphs.
Ideal for level-order traversal: When you need to process data level by level, like printing nodes at each depth of a tree.

DFS:

Use when you need to explore as deeply as possible first: DFS goes deep down a path, which can be useful in scenarios where you need to fully explore one option before moving to the next.
Backtracking problems: DFS is a great tool for solving puzzles or games that require backtracking (like Sudoku or maze generation).

Recursive DFS Implementation:

DFS can also be easily implemented using recursion, which leverages the call stack:

function dfsRecursive(graph, node, visited = new Set()) {
  if (!visited.has(node)) {
    console.log(node); // Process node
    visited.add(node);
    graph[node].forEach(neighbor => dfsRecursive(graph, neighbor, visited));
  }
}

// Traverse starting from node 1
dfsRecursive(graph, 1);

Visualizing BFS and DFS:

To better grasp these concepts, imagine a tree structure where BFS explores each level horizontally, while DFS dives straight down a branch vertically.

BFS: Explores nodes in layers (e.g., 1 → 2, 3 → 4, 5, 6).
DFS: Dives deep into the leftmost branch first (e.g., 1 → 2 → 4), then backtracks.

Conclusion

Mastering BFS and DFS opens up a wide range of possibilities in solving complex problems, from finding the shortest path in a network to traversing hierarchical data. While BFS is great for exploring level by level and finding the shortest path, DFS helps in deep explorations and solving backtracking problems.

With the examples above, you’re ready to dive deeper into these search algorithms. Next time you’re faced with a tree or graph traversal problem, you’ll know whether to go wide (BFS) or go deep (DFS).

Happy coding!