What is the time complexity of DFS?

DFS runs in O(V + E) time, where V is the number of vertices and E is the number of edges. It visits each vertex and edge exactly once.

Is DFS or BFS better?

Neither is universally better — it depends on the problem. DFS uses less memory and is better for deep graphs, topological sorting, and cycle detection. BFS is better for finding shortest paths in unweighted graphs and level-order exploration.

Does DFS find the shortest path?

No. DFS finds a path but not necessarily the shortest one. It explores deeply along each branch, so it may find a longer path before a shorter one. Use BFS for shortest paths in unweighted graphs.

DFS Visualizer

Visualize Depth-First Search as it dives deep into a graph before backtracking. Build your own graph, pick a starting node, and watch DFS explore every path to its end.

Visualize DFS

How It Works

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) to keep track of which nodes to visit next.

DFS is fundamental in computer science and forms the basis for many other algorithms including topological sorting, cycle detection, and finding connected components. It was first investigated by Charles Pierre Trémaux as a strategy for solving mazes.

1
Start at the source node and mark it as visited
2
Push the source node onto the stack
3
Pop the top node from the stack
4
Visit an unvisited neighbor of the current node and push it onto the stack
5
If no unvisited neighbors remain, backtrack by popping the stack
6
Repeat until the stack is empty

Key Properties

Time Complexity

O(V + E) where V is the number of vertices and E is the number of edges in the graph.

Depth-First

Explores as deep as possible along each branch before backtracking to explore other paths.

Stack-Based

Uses a LIFO stack (or recursion call stack) to track the current exploration path.

Complete Traversal

Visits every reachable node exactly once, making it useful for exhaustive graph exploration.

Common Use Cases

Maze solving — exploring paths to find a way through a labyrinth
Topological sorting — ordering tasks with dependencies in build systems
Connected components — finding isolated groups in a network

Frequently Asked Questions

What is 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) to track the current path and visits every reachable node exactly once.
What is the time complexity of DFS?: DFS runs in O(V + E) time, where V is the number of vertices and E is the number of edges. It visits each vertex and edge exactly once.
Is DFS or BFS better?: Neither is universally better — it depends on the problem. DFS uses less memory and is better for deep graphs, topological sorting, and cycle detection. BFS is better for finding shortest paths in unweighted graphs and level-order exploration.
Does DFS find the shortest path?: No. DFS finds a path but not necessarily the shortest one. It explores deeply along each branch, so it may find a longer path before a shorter one. Use BFS for shortest paths in unweighted graphs.

Ready to see it in action?

Open the Visualizer