AV
LibraryGraph DFS

Graph DFS

Medium

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Used for topological sorting and cycle detection.

Time Complexity

O(V + E)

Space Complexity

O(V)

Category

Graph

Introduction to Depth-First Search (DFS)

DFS is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's one of the most important algorithms for graph problems and has numerous applications.

How It Works

DFS can be implemented using recursion or an explicit stack:

**Recursive Approach**:

1. Visit a vertex and mark it as visited

2. Recursively visit all unvisited neighbors

3. Backtrack when all neighbors are visited

**Stack-based Approach**:

1. Push starting vertex onto stack

2. While stack is not empty:

- Pop vertex from stack

- If not visited, mark as visited

- Push all unvisited neighbors

Algorithm Complexity

**Time Complexity**: O(V + E) - Visit each vertex and edge once
**Space Complexity**: O(V) - For the visited set and recursion stack

Key Characteristics

1. Uses stack (LIFO) - either explicit or call stack

2. Explores deeply before exploring siblings

3. Can find connected components

4. Good for topological sorting

5. Useful for cycle detection

Advantages

1. Simple implementation using recursion

2. Memory efficient for breadth-limited graphs

3. Good for finding connectivity

4. Useful for topological sorting

5. Natural for problems requiring path finding

Disadvantages

1. May use significant stack space for deep graphs

2. Not optimal for finding shortest paths

3. Can be slower than BFS for certain problems

4. May revisit the same path in complex graphs

When to Use

**Topological sorting**: Ordering tasks with dependencies
**Cycle detection**: Finding cycles in directed graphs
**Connected components**: Finding isolated subgraphs
**Path finding**: Finding any path between vertices
**Maze solving**: Finding way out of maze
**Strongly connected components**: Using Kosaraju's algorithm

Applications

Social networks (friend recommendations)
Web crawlers (following links)
Compiler design (determining dependencies)
Game tree search (AI algorithms)
Puzzle solving
Undo functionality (using call stack)

Comparison with BFS

**DFS**: Goes deep, uses stack, good for topological sort
**BFS**: Goes wide, uses queue, finds shortest paths
**Memory**: DFS better for tall graphs, BFS better for wide
**Applications**: DFS for connectivity, BFS for shortest path

Key Takeaways

  • Explores deeply first
  • Uses stack or recursion
  • Backtracking approach
  • Useful for topological sorting
  • Detects cycles in graphs
  • Space-efficient with recursion

Implementation

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);
  
  for (let neighbor of graph[start] || []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
  
  return visited;
}

Tags

graphtraversalrecursiveintermediate

Quick Stats

Difficulty:Medium
Type:Graph

Share