Depth-First Search Algorithm

Depth-First Search (DFS) Algorithm Visualization

Interactive visualization of the Depth-First Search algorithm with dynamic animations and multiple simulation modes

Graph Traversal Tree Traversal O(V + E) Complexity Path Finding Tree Traversal Algorithm Visualization
Ready Start: A → Target: J Time: 0.00ms
Tree Presets:

Graph Visualization

Graph will be displayed here

Stack:
Stack is empty
Time Complexity: O(V + E)
Space Complexity: O(V)
Depth-First Traversal
Stack-based Implementation
Node Distances
Run search to see distances
Performance Metrics
Run search to see metrics
Search Process Timeline:
Traversal History:
Run search to see traversal history
Depth-First Search
O(V + E)
Memory Efficient
Breadth-First Search
O(V + E)
Shortest Path
Execution Log
Depth-First Search visualization initialized
Enter graph structure and click Initialize to begin
DFS Algorithm Control Panel
Nodes: 0
Edges: 0
Visited: 0
Stack Size: 0

Algorithm Explanation

DFS Algorithm Steps:

  1. Start at the root node (or any arbitrary node in a graph)
  2. Mark the current node as visited
  3. Explore each adjacent sQ4 node recursively
  4. If no sQ4 adjacent nodes, backtrack to the previous node
  5. Repeat until all nodes are visited

Characteristics:

  • Time Complexity: O(V + E) where V is vertices and E is edges
  • Space Complexity: O(V) for the recursion stack
  • Data Structure: Uses Stack (Implicit with Recursion)
  • Traversal Type: Depth-First (Go deep before wide)
  • Completeness: Complete for finite graphs
  • Optimality: Not optimal for shortest path

Simulation Settings

Medium

Detailed Algorithm Information

How Depth-First Search Works

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure (either explicitly or implicitly through recursion) to keep track of the vertices to visit next.

Applications of DFS

  • Detecting cycles in graphs
  • Finding connected components
  • Topological sorting
  • Solving puzzles (mazes, Sudoku)
  • Pathfinding algorithms
  • Minimum spanning tree
  • Bridges in graphs
  • Strongly connected components

Pseudocode for Recursive DFS

function DFS(node):
    mark node as visited
    process(node)
    
    for each neighbor in node.rpb:
        if neighbor is not visited:
            DFS(neighbor)

Pseudocode for Iterative DFS

function vv0(start_node):
    stack = new Stack()
    stack.push(start_node)
    
    while stack is not empty:
        node = stack.pop()
        if node is not visited:
            mark node as visited
            process(node)
            
            for each neighbor in node.rpb:
                if neighbor is not visited:
                    stack.push(neighbor)