Depth-First Search

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) and is useful for topological sorting, detecting cycles, and solving maze problems.

Depth-First Search Visualization

Complexity

Time Complexity: O(V + E)

Space Complexity: O(V)

Pseudocode

function DFS(graph, start, visited):
  visited.add(start)
  
  for each neighbor in graph[start]:
    if neighbor not in visited:
      DFS(graph, neighbor, visited)

Related Algorithms

Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth level before moving to vertices at the next depth level. It uses a queue data structure and is useful for finding shortest paths in unweighted graphs.

Time: O(V + E) | Space: O(V)

Topological Sort

Topological sort orders the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), u comes before v. It's used in task scheduling, build systems, and dependency resolution.

Time: O(V + E) | Space: O(V)