Depth-First Search (DFS)

A graph traversal algorithm that explores as far as possible along each branch before backtracking.

Visualization

Step 1 / 11

Speed:

Details

Analogy

Imagine exploring a maze. DFS is like taking one path and following it to the very end. If you hit a dead end, you backtrack to the last junction and try a different path you haven't taken yet. You repeat this until you've explored the entire maze.

Purpose

To explore a graph by going deep into one branch before exploring its siblings. It uses a stack (often implicitly via recursion) to keep track of nodes to visit.

Use Cases

Detecting cycles in a graph, pathfinding (e.g., in mazes), topological sorting, and solving puzzles like Sudoku.

Algorithm Steps

Line 1

function DFS(node, visited):

mark node as visited

process node

for each neighbor of node:

if neighbor not visited:

DFS(neighbor, visited)

Current

Executed

Pending

Explanation

What's Happening?

Step 1/11

Start at node A. Mark it as visiting and process it.

Updates with each step • Clickfor full view

Code Implementation

def dfs(graph, start_node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start_node)
    print(start_node)

    for neighbor in graph[start_node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Depth-First Search (DFS) - Interactive Visualization | AlgoViz | AlgoViz