Applications of BFS and DFS in JavaScript

8.2.3 Applications of BFS and DFS

Breadth-First Search (BFS) and Depth-First Search (DFS) are fundamental graph traversal algorithms that are pivotal in solving various computational problems. Understanding their applications is crucial for leveraging their strengths in different scenarios. In this section, we will explore the practical applications of BFS and DFS, provide code examples, and discuss when to use each algorithm based on problem requirements.

Key Learning Objectives

• Explore practical applications of BFS and DFS algorithms.
• Learn when to use BFS versus DFS based on problem requirements.
• Understand how traversal methods impact algorithm outcomes.

Applications of BFS

Breadth-First Search is a level-order traversal technique that explores all neighbors of a node before moving to the next level. This characteristic makes BFS suitable for several applications:

Finding Shortest Path in Unweighted Graphs

BFS is ideal for finding the shortest path in unweighted graphs because it explores all nodes at the present depth level before moving on to nodes at the next depth level. This ensures that the first time we reach a node, we have found the shortest path to it.

Example: Shortest Path Using BFS

function shortestPathBFS(graph, startVertex, targetVertex) {
  const queue = [startVertex];
  const visited = new Set();
  const predecessor = {};
  visited.add(startVertex);
  
  while (queue.length > 0) {
    const vertex = queue.shift();
    if (vertex === targetVertex) {
      // Build path from predecessors
      const path = [];
      let current = targetVertex;
      while (current !== undefined) {
        path.unshift(current);
        current = predecessor[current];
      }
      return path;
    }
    const neighbors = graph.getNeighbors(vertex);
    for (let neighbor of neighbors) {
      if (!visited.has(neighbor.node)) {
        visited.add(neighbor.node);
        predecessor[neighbor.node] = vertex;
        queue.push(neighbor.node);
      }
    }
  }
  return null; // Path not found
}

Level Order Traversal in Trees

In tree data structures, BFS is used for level order traversal, which processes nodes level by level. This is particularly useful in scenarios such as printing a tree’s structure or processing nodes in a breadth-wise manner.

Web Crawling

Web crawlers use BFS to traverse web pages. Starting from a set of seed URLs, BFS can be used to explore all reachable pages level by level. This ensures that all pages at a certain depth are indexed before moving deeper.

Social Networking

In social networks, BFS can be used to find people within a certain degree of connection. For example, finding all friends of friends within two degrees of separation can be efficiently done using BFS.

Applications of DFS

Depth-First Search explores as far as possible along each branch before backtracking. This depth-wise exploration is beneficial in several scenarios:

Cycle Detection

DFS is commonly used for detecting cycles in graphs. By keeping track of visited nodes and the recursion stack, DFS can identify back edges, which indicate cycles.

Example: Cycle Detection Using DFS

function hasCycle(graph) {
  const visited = new Set();
  const stack = new Set();

  function dfs(vertex) {
    if (stack.has(vertex)) return true;
    if (visited.has(vertex)) return false;

    visited.add(vertex);
    stack.add(vertex);

    const neighbors = graph.getNeighbors(vertex);
    for (let neighbor of neighbors) {
      if (dfs(neighbor.node)) return true;
    }

    stack.delete(vertex);
    return false;
  }

  for (let vertex of graph.getVertices()) {
    if (dfs(vertex)) return true;
  }
  return false;
}

Topological Sorting

Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge UV from vertex U to vertex V, U comes before V in the ordering. DFS is used to perform topological sorting by visiting nodes in post-order.

Solving Mazes

DFS is effective for solving maze problems where all possible paths need to be explored. By exploring each path to its fullest before backtracking, DFS can find a solution path or determine that no path exists.

Choosing Between BFS and DFS

The choice between BFS and DFS depends on the specific problem requirements:

• Use BFS when you need to find the shortest path in an unweighted graph or when exploring nodes level by level is beneficial.
• Use DFS when you need to explore all possible paths or when depth-wise exploration is more suitable, such as in cycle detection or topological sorting.

Practice Problems

To solidify your understanding of BFS and DFS, consider implementing the following practice problems:

1. Detect if a Graph is Bipartite Using BFS: Implement an algorithm to check if a graph can be colored using two colors such that no two adjacent vertices share the same color.

2. Find Connected Components in an Undirected Graph Using DFS: Use DFS to identify all connected components in an undirected graph.

Conclusion

BFS and DFS are powerful algorithms with distinct applications. By understanding their strengths and limitations, you can choose the appropriate algorithm for your specific problem. Whether it’s finding the shortest path, detecting cycles, or exploring all possible solutions, BFS and DFS provide the foundational tools needed for effective graph traversal.

Quiz Time!