Depth-First Search

Graphmedium#10

Explore as deep as possible before backtracking — uses stack

Ready

Step 1 of 0

Speed

Algorithm Code

1function dfs(grid, start, end) {
2  const stack = [start];
3  const visited = new Set();
4  while (stack.length > 0) {
5    const [r, c] = stack.pop();
6    if (visited.has(key(r,c))) continue;
7    visited.add(key(r, c));
8    if (r === end[0] && c === end[1]) return true;
9    for (const [dr, dc] of dirs) {
10      const nr = r+dr, nc = c+dc;
11      if (valid(nr,nc) && !visited.has(key(nr,nc)))
12        stack.push([nr, nc]);
13    }
14  }
15  return false;
16}

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

About Depth-First Search

DFS explores as far as possible along each branch before backtracking. It uses a stack (LIFO) and is ideal for topological sorting, cycle detection, maze solving, and finding connected components. Does not guarantee shortest path in unweighted graphs.

Time Complexity: Best: O(V + E), Average: O(V + E), Worst: O(V + E). Space: O(V).

Depth-First Search

Graphmedium#10

Explore as deep as possible before backtracking — uses stack

Ready

Step 1 of 0

Speed

Algorithm Code

1function dfs(grid, start, end) {
2  const stack = [start];
3  const visited = new Set();
4  while (stack.length > 0) {
5    const [r, c] = stack.pop();
6    if (visited.has(key(r,c))) continue;
7    visited.add(key(r, c));
8    if (r === end[0] && c === end[1]) return true;
9    for (const [dr, dc] of dirs) {
10      const nr = r+dr, nc = c+dc;
11      if (valid(nr,nc) && !visited.has(key(nr,nc)))
12        stack.push([nr, nc]);
13    }
14  }
15  return false;
16}

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

About Depth-First Search

Time Complexity: Best: O(V + E), Average: O(V + E), Worst: O(V + E). Space: O(V).