Skip to main content

Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

It's a recursive algorithm that uses the idea of backtracking to explore all vertices and edges in a graph.

DFS is commonly used in graph problems like finding connected components, topological sorting, and solving puzzles.

Algorithm​

The DFS algorithm follows these steps:

  1. Start from a vertex V and mark it as visited.
  2. For each unvisited neighbor U of V, visit U recursively.
  3. Repeat the process until all vertices are visited.

Here's a basic template of a DFS algorithm in JavaScript:

function dfs(graph, start, visited) {
  visited[start] = true;

  for (const neighbor of graph[start]) {
    if (!visited[neighbor]) {
      dfs(graph, neighbor, visited);
    }
  }
}

Example​

Given a graph defined as an adjacency list. Each node has a list of its neighbors. You are required to print all nodes in the graph using DFS algorithm.

Mark and Sweep Algorithm in JS 
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const dfs = (node, visited = new Set()) => {
  if (visited.has(node)) return;

  console.log(node);
  visited.add(node);

  for (const neighbor of graph[node]) {
    dfs(neighbor, visited);
  }
}

dfs("A");
// Output: A -> B -> D -> E -> F -> C