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

How to use the DFS Visualizer

  1. Create nodes: click on the graph canvas to add vertices.
  2. Connect nodes: click one node, then click another to create an edge.
  3. Start the algorithm: click Start Step or Run to begin the DFS traversal.
  4. Follow the process: watch the queue and logs to understand each step.

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)