DFS & BFS on Graphs

Depth-First Search (DFS) on Graphs

Depth-First Search (DFS) is a fundamental algorithm for traversing or searching through graph data structures. The algorithm starts at a given node and explores as far as possible along each branch before backtracking.

How DFS Works

DFS can be implemented using either a recursive approach or an iterative approach with a stack. The key idea is to start from a source node, visit its adjacent nodes, and continue this process until all nodes reachable from the source are visited.

Pseudocode

Here's the pseudocode for a recursive DFS on an undirected graph:

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B'],
  F: ['C'],
  G: ['L'],
  M: ['S']
};

Recusrive DFS

const dfs = (graph, startNode, visited = new Set()) => {
  visited.add(startNode);
  console.log(startNode);

  for (const neighbour of graph[startNode] || []) {
    if (!visited.has(neighbour)) {
      dfs(graph, neighbour, visited);
    }
  }
};

const visited = new Set();

// To handle disconnected components, loop through all nodes
for (const node of Object.keys(graph)) {
  if (!visited.has(node)) {
    dfs(graph, node, visited);
  }
}

Iterative DFS

const dfsIterative = (graph, start, visited = new Set()) => {
  const stack = [start]
  visited.add(start)

  while (stack.length) {
    const current = stack.pop()
    console.log(current);
    for (const neighbour of graph[current]) {
      if (!visited.has(neighbour)) {
        stack.push(neighbour)
        visited.add(neighbour)
      }
    }

  }
}

// To handle disconnected components, loop through all nodes
const allNodes = new Set(Object.keys(graph));
const visited = new Set();

for (const node of allNodes) {
  if (!visited.has(node)) {
    dfsIterative(graph, node, visited);
  }
}

Breadth-First Search (BFS) on Graphs

Breadth-First Search (BFS) is an algorithm used for traversing or searching through graph or tree data structures. The algorithm starts at a given node and explores all of its neighbors at the present depth before moving on to nodes at the next depth level.

How BFS Works

BFS is typically implemented using a queue data structure. It starts from a source node and explores all of its neighbors first before moving on to the next layer of nodes. This ensures that nodes are visited in the order of their distance from the source node.

Pseudocode

Here’s the pseudocode for BFS on an undirected graph:

BFS

const bfs = (graph, start, visited = new Set()) => {
  const queue = [start]
  visited.add(start)

  while (queue.length) {
    const current = queue.shift()
    console.log(current);
    for (const neighbour of graph[current]) {
      if (!visited.has(neighbour)) {
        queue.push(neighbour)
        visited.add(neighbour)
      }
    }
  }
}

// To handle disconnected components, loop through all nodes
const allNodes = new Set(Object.keys(graph));
const visited = new Set();

for (const node of allNodes) {
  if (!visited.has(node)) {
    bfs(graph, node, visited);
  }
}

Shortest Path Using BFS

const bfsShortestPath = (graph, start, end) => {
  const queue = [[start]];
  const visited = new Set();

  while (queue.length > 0) {
    const path = queue.shift(); // Get the current path
    const node = path[path.length - 1]; // Get the last node in the path

    if (node === end) {
      return path; // Return the path if we've reached the end
    }

    if (!visited.has(node)) {
      visited.add(node); // Mark the node as visited

      for (const neighbor of graph[node] ?? []) {
        // Create a new path to the neighbor and enqueue it
        const newPath = [...path, neighbor];
        queue.push(newPath);
      }
    }
  }

  return []; // Return an empty array if there's no path to the end
}

// Example usage with disconnected vertices:
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E'],
  G: [], // Disconnected vertex G
};

const shortestPath1 = bfsShortestPath(graph, 'A', 'F');
console.log(shortestPath1); // Output: ['A', 'C', 'F']

const shortestPath2 = bfsShortestPath(graph, 'A', 'G');
console.log(shortestPath2); // Output: [] (no path to G)

Shortest Path Using BFS for a 2D Grid

const bfsShortestPath = (grid, start, end) => {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]; // Down, Right, Up, Left
  const queue = [[...start, 0]]; // [row, col, distance]
  const visited = new Set(); // To track visited cells
  visited.add(start.toString()); // Mark the start cell as visited

  while (queue.length > 0) {
    const [row, col, distance] = queue.shift(); // Dequeue

    // Check if we reached the end
    if (row === end[0] && col === end[1]) {
      return distance; // Return the distance (shortest path length)
    }

    // Explore the neighbors
    for (const [dRow, dCol] of directions) {
      const newRow = row + dRow;
      const newCol = col + dCol;

      // Check if the new position is within bounds and not visited
      if (
        newRow >= 0 &&
        newRow < rows &&
        newCol >= 0 &&
        newCol < cols &&
        grid[newRow][newCol] === 0 && // Assuming 0 is a valid cell
        !visited.has([newRow, newCol].toString())
      ) {
        visited.add([newRow, newCol].toString()); // Mark as visited
        queue.push([newRow, newCol, distance + 1]); // Enqueue with increased distance
      }
    }
  }

  return -1; // Return -1 if there's no path
}

// Example usage:
const grid = [
  [0, 0, 0, 1],
  [0, 1, 0, 0],
  [0, 0, 0, 0],
  [1, 0, 1, 0]
];

const start = [0, 0]; // Starting position
const end = [3, 3];   // Ending position

const shortestPathLength = bfsShortestPath(grid, start, end);
console.log(shortestPathLength); // Should output: 6