onenoughtone

Introduction to Depth-First Search

What is Depth-First Search?

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

In simpler terms, DFS explores a path all the way to its end before moving on to the next path, going deep before going wide.

Key Characteristics

Stack-Based: Uses a stack data structure (or recursion) to keep track of vertices to visit
Deep Exploration: Explores as far as possible along each branch before backtracking
Memory Efficient: Requires less memory than breadth-first search
Not Optimal for Shortest Paths: Does not guarantee the shortest path in unweighted graphs
Complete: Will find a solution if one exists in a finite graph

How DFS Works

Start at a source vertex and mark it as visited
Explore one of its unvisited neighbors
Continue this process, always exploring an unvisited neighbor of the most recently visited vertex
When a vertex has no unvisited neighbors, backtrack to the previous vertex and explore its other neighbors
Repeat until all vertices reachable from the source are visited

Basic DFS Implementation

Here's a simple recursive implementation of DFS for a graph represented as an adjacency list:

Iterative DFS Implementation

Here's an iterative implementation of DFS using a stack:

Time and Space Complexity

Time Complexity:

O(V + E), where V is the number of vertices and E is the number of edges in the graph.

We visit each vertex once and each edge once.

Space Complexity:

O(V), where V is the number of vertices in the graph.

In the worst case, the stack might contain all vertices of the graph. For recursive implementation, the call stack might grow to size V.

Applications of DFS

Backtracking: Solving puzzles, generating mazes, and combinatorial problems
Cycle Detection: Finding cycles in a graph
Topological Sorting: Ordering vertices such that for every directed edge (u, v), vertex u comes before v
Connected Components: Finding all connected components in a graph
Pathfinding: Finding a path between two vertices
Strongly Connected Components: Finding strongly connected components in a directed graph

Home Next

Learning Objective

Understand the fundamental concepts of depth-first search and its importance in graph traversal, backtracking, and cycle detection.

What is Depth-First Search?

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

In simpler terms, DFS explores a path all the way to its end before moving on to the next path, going deep before going wide.

Think of DFS as exploring a maze by following a single path until you hit a dead end, then backtracking to the last intersection and trying a different path.

Key Characteristics

Stack-Based

Uses a stack data structure (or recursion) to keep track of vertices to visit, following a Last In, First Out (LIFO) approach.

Deep Exploration

Explores as far as possible along each branch before backtracking, creating a depth-wise exploration.

Memory Efficient

Requires less memory than breadth-first search because it only needs to store the vertices on the current path.

Not Optimal for Shortest Paths

Does not guarantee the shortest path in unweighted graphs, as it might explore a long path first.

How DFS Works

1Start

Begin at a source vertex, mark it as visited, and process it (e.g., add to result).

2Explore

Choose one of its unvisited neighbors and recursively apply DFS to that neighbor.

3Go Deep

Continue this process, always exploring an unvisited neighbor of the most recently visited vertex.

4Backtrack

When a vertex has no unvisited neighbors, backtrack to the previous vertex and explore its other neighbors.

5Complete

Repeat until all vertices reachable from the source are visited.

Recursive DFS Implementation

Here's a recursive implementation of DFS for a graph represented as an adjacency list:

dfs.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function dfs(graph, startVertex) {
  // Set to keep track of visited vertices
  const visited = new Set();
 
  // Result array to store the DFS traversal order
  const result = [];
 
  // Recursive helper function
  function dfsHelper(vertex) {
    // Mark the vertex as visited
    visited.add(vertex);
 
    // Process the vertex (add to result)
    result.push(vertex);
 
    // Explore all adjacent vertices
    for (const neighbor of graph[vertex]) {
      // If this neighbor has not been visited yet
      if (!visited.has(neighbor)) {
        // Recursively visit the neighbor
        dfsHelper(neighbor);
      }
    }
  }
 
  // Start DFS from the start vertex
  dfsHelper(startVertex);
 
  return result;
}
 
// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};
 
const traversalOrder = dfs(graph, 'A');
console.log(traversalOrder); // Output: ['A', 'B', 'D', 'E', 'F', 'C']

Note: The recursive implementation is elegant and intuitive, but it may cause a stack overflow for very deep graphs. In such cases, the iterative implementation is preferred.

Iterative DFS Implementation

Here's an iterative implementation of DFS using a stack:

dfsIterative.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function dfsIterative(graph, startVertex) {
  // Set to keep track of visited vertices
  const visited = new Set();
 
  // Stack for DFS (using array as stack)
  const stack = [startVertex];
 
  // Result array to store the DFS traversal order
  const result = [];
 
  // Mark the start vertex as visited
  visited.add(startVertex);
 
  // While there are vertices in the stack
  while (stack.length > 0) {
    // Pop a vertex from the stack
    const currentVertex = stack.pop();
 
    // Process the vertex (add to result)
    result.push(currentVertex);
 
    // Get all adjacent vertices of the popped vertex
    // Add unvisited neighbors to the stack in reverse order
    // (to match the recursive implementation)
    for (const neighbor of [...graph[currentVertex]].reverse()) {
      if (!visited.has(neighbor)) {
        // Mark it as visited and push it to the stack
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
 
  return result;
}
 
// Example usage:
const traversalOrderIterative = dfsIterative(graph, 'A');
console.log(traversalOrderIterative); // Output: ['A', 'B', 'D', 'E', 'F', 'C']

Key Insight: The iterative implementation explicitly uses a stack to mimic the call stack of the recursive implementation. Note that we process neighbors in reverse order to match the recursive implementation's traversal order.

Time and Space Complexity

Time Complexity

O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Explanation: In the worst case, we visit each vertex once (O(V)) and explore each edge once (O(E)). For a connected graph, E is at least V-1, so the time complexity is dominated by the number of edges.

Space Complexity

O(V), where V is the number of vertices in the graph.

Explanation: We need to store the visited set (O(V)) and the stack (O(V) in the worst case). For the recursive implementation, the call stack might grow to size V in the worst case. Overall, the space complexity is O(V).

Comparison with BFS

Both DFS and BFS have the same time complexity (O(V + E)), but DFS typically requires less memory because it only needs to store the vertices on the current path, whereas BFS needs to store all vertices at the current level.

Applications of DFS

Backtracking

DFS is the backbone of backtracking algorithms, which are used to solve puzzles, generate mazes, and solve combinatorial problems like N-Queens and Sudoku.

Cycle Detection

DFS can be used to detect cycles in a graph by keeping track of vertices in the current recursion stack.

Topological Sorting

DFS can be used to perform a topological sort of a directed acyclic graph (DAG), which is useful for scheduling tasks with dependencies.

Connected Components

DFS can be used to find all connected components in an undirected graph and strongly connected components in a directed graph.

DFS vs BFS: When to Use Each

Use DFS When

You need to explore all possible paths (e.g., maze solving)
You're implementing backtracking algorithms
You need to detect cycles in a graph
You need to perform a topological sort
Memory is a concern (DFS uses less memory than BFS)

Use BFS When

You need to find the shortest path in an unweighted graph
You need to explore vertices level by level
You're working with a graph where the solution is likely to be closer to the source
You need to find all vertices at a given distance from the source
You're working with a graph that might have infinite depth

Home Next: DFS Visualization

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Depth-First Search in DSA

Introduction to Depth-First Search

What is Depth-First Search?

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

In simpler terms, DFS explores a path all the way to its end before moving on to the next path, going deep before going wide.

Key Characteristics

Stack-Based: Uses a stack data structure (or recursion) to keep track of vertices to visit
Deep Exploration: Explores as far as possible along each branch before backtracking
Memory Efficient: Requires less memory than breadth-first search
Not Optimal for Shortest Paths: Does not guarantee the shortest path in unweighted graphs
Complete: Will find a solution if one exists in a finite graph

How DFS Works

Start at a source vertex and mark it as visited
Explore one of its unvisited neighbors
Continue this process, always exploring an unvisited neighbor of the most recently visited vertex
When a vertex has no unvisited neighbors, backtrack to the previous vertex and explore its other neighbors
Repeat until all vertices reachable from the source are visited

Basic DFS Implementation

Here's a simple recursive implementation of DFS for a graph represented as an adjacency list:

Iterative DFS Implementation

Here's an iterative implementation of DFS using a stack:

Time and Space Complexity

Time Complexity:

O(V + E), where V is the number of vertices and E is the number of edges in the graph.

We visit each vertex once and each edge once.

Space Complexity:

O(V), where V is the number of vertices in the graph.

In the worst case, the stack might contain all vertices of the graph. For recursive implementation, the call stack might grow to size V.

Applications of DFS

Backtracking: Solving puzzles, generating mazes, and combinatorial problems
Cycle Detection: Finding cycles in a graph
Topological Sorting: Ordering vertices such that for every directed edge (u, v), vertex u comes before v
Connected Components: Finding all connected components in a graph
Pathfinding: Finding a path between two vertices
Strongly Connected Components: Finding strongly connected components in a directed graph

Home Next

Learning Objective

Understand the fundamental concepts of depth-first search and its importance in graph traversal, backtracking, and cycle detection.

What is Depth-First Search?

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

In simpler terms, DFS explores a path all the way to its end before moving on to the next path, going deep before going wide.

Think of DFS as exploring a maze by following a single path until you hit a dead end, then backtracking to the last intersection and trying a different path.

Key Characteristics

Stack-Based

Uses a stack data structure (or recursion) to keep track of vertices to visit, following a Last In, First Out (LIFO) approach.

Deep Exploration

Explores as far as possible along each branch before backtracking, creating a depth-wise exploration.

Memory Efficient

Requires less memory than breadth-first search because it only needs to store the vertices on the current path.

Not Optimal for Shortest Paths

Does not guarantee the shortest path in unweighted graphs, as it might explore a long path first.

How DFS Works

1Start

Begin at a source vertex, mark it as visited, and process it (e.g., add to result).

2Explore

Choose one of its unvisited neighbors and recursively apply DFS to that neighbor.

3Go Deep

Continue this process, always exploring an unvisited neighbor of the most recently visited vertex.

4Backtrack

When a vertex has no unvisited neighbors, backtrack to the previous vertex and explore its other neighbors.

5Complete

Repeat until all vertices reachable from the source are visited.

Recursive DFS Implementation

Here's a recursive implementation of DFS for a graph represented as an adjacency list:

dfs.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function dfs(graph, startVertex) {
  // Set to keep track of visited vertices
  const visited = new Set();
 
  // Result array to store the DFS traversal order
  const result = [];
 
  // Recursive helper function
  function dfsHelper(vertex) {
    // Mark the vertex as visited
    visited.add(vertex);
 
    // Process the vertex (add to result)
    result.push(vertex);
 
    // Explore all adjacent vertices
    for (const neighbor of graph[vertex]) {
      // If this neighbor has not been visited yet
      if (!visited.has(neighbor)) {
        // Recursively visit the neighbor
        dfsHelper(neighbor);
      }
    }
  }
 
  // Start DFS from the start vertex
  dfsHelper(startVertex);
 
  return result;
}
 
// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};
 
const traversalOrder = dfs(graph, 'A');
console.log(traversalOrder); // Output: ['A', 'B', 'D', 'E', 'F', 'C']

Note: The recursive implementation is elegant and intuitive, but it may cause a stack overflow for very deep graphs. In such cases, the iterative implementation is preferred.

Iterative DFS Implementation

Here's an iterative implementation of DFS using a stack:

dfsIterative.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function dfsIterative(graph, startVertex) {
  // Set to keep track of visited vertices
  const visited = new Set();
 
  // Stack for DFS (using array as stack)
  const stack = [startVertex];
 
  // Result array to store the DFS traversal order
  const result = [];
 
  // Mark the start vertex as visited
  visited.add(startVertex);
 
  // While there are vertices in the stack
  while (stack.length > 0) {
    // Pop a vertex from the stack
    const currentVertex = stack.pop();
 
    // Process the vertex (add to result)
    result.push(currentVertex);
 
    // Get all adjacent vertices of the popped vertex
    // Add unvisited neighbors to the stack in reverse order
    // (to match the recursive implementation)
    for (const neighbor of [...graph[currentVertex]].reverse()) {
      if (!visited.has(neighbor)) {
        // Mark it as visited and push it to the stack
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
 
  return result;
}
 
// Example usage:
const traversalOrderIterative = dfsIterative(graph, 'A');
console.log(traversalOrderIterative); // Output: ['A', 'B', 'D', 'E', 'F', 'C']

Time and Space Complexity

Time Complexity

O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity

O(V), where V is the number of vertices in the graph.

Comparison with BFS

Applications of DFS

Backtracking

DFS is the backbone of backtracking algorithms, which are used to solve puzzles, generate mazes, and solve combinatorial problems like N-Queens and Sudoku.

Cycle Detection

DFS can be used to detect cycles in a graph by keeping track of vertices in the current recursion stack.

Topological Sorting

DFS can be used to perform a topological sort of a directed acyclic graph (DAG), which is useful for scheduling tasks with dependencies.

Connected Components

DFS can be used to find all connected components in an undirected graph and strongly connected components in a directed graph.

DFS vs BFS: When to Use Each

Use DFS When

You need to explore all possible paths (e.g., maze solving)
You're implementing backtracking algorithms
You need to detect cycles in a graph
You need to perform a topological sort
Memory is a concern (DFS uses less memory than BFS)

Use BFS When

You need to find the shortest path in an unweighted graph
You need to explore vertices level by level
You're working with a graph where the solution is likely to be closer to the source
You need to find all vertices at a given distance from the source
You're working with a graph that might have infinite depth

Home Next: DFS Visualization