Depth First Search (DFS)

Depth-First Search is a graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking.

It dives deep into the graph rather than traversing it level by level.

It uses a stack (either explicitly or through recursion) to keep track of the path.

How Depth-First Search Works?

Start at a given source node.
Mark the node as visited.
For each unvisited neighbor, recursively apply DFS.
If there are no unvisited neighbors, backtrack to the previous node.
Repeat until all nodes are visited.

Example: Depth-First Search

Graph,

A - B
|   |
C - D

Adjacency List (Edges)

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Depth-First Search Traversal from Vertex A. We use a visited set to keep track of visited nodes.

Step 1: Start at A

Mark A as visited: {A}
A’s neighbors: B, C → Start with B
Recurse into B

Step 2: Visit B

Mark B as visited: {A, B}
B’s neighbors: A (already visited), D → Visit D
Recurse into D

Step 3: Visit D

Mark D as visited: {A, B, D}
D’s neighbors: B (visited), C → Visit C
Recurse into C

Step 4: Visit C

Mark C as visited: {A, B, D, C}
C’s neighbors: A, D (both already visited)
Done with C → backtrack to D → B → A

Order: A → B → D → C (depending on adjacency order)

Time and Space Complexity

Let,

V = number of vertices
E = number of edges

Time Complexity: O(V + E) each node and edge is visited once.

Space Complexity: O(V) for visited set and recursion stack (or explicit stack).

Applications of Depth-First Search

Maze or Puzzle Solving
Topological Sorting (e.g., course scheduling)
Cycle Detection in a graph
Finding Connected Components
Solving Problems in AI (e.g., game trees, planning)
Detecting Bridges and Articulation Points in a network

Advantages of Depth First Search

Low Memory Usage

DFS uses memory proportional to the depth of the tree or graph, unlike Breadth-First Search (BFS), which uses memory proportional to the breadth (number of neighbors at each level).

Space Complexity: O(V) in the worst case (for the recursion stack)

Simple Implementation

DFS is easier to implement using recursion or a stack, and requires less auxiliary data structures compared to BFS.

Works Well with Graph Structures

DFS is suitable for,

Detecting cycles
Topological sorting
Strongly connected components (SCCs)
Solving mazes and puzzles (e.g., backtracking algorithms like Sudoku, N-Queens)

Finds a Solution Without Exploring All Nodes

In some problems (like pathfinding), DFS might reach the goal early without visiting all vertices, especially if the solution lies deep in the graph.

Useful for Backtracking

DFS is ideal for problems where you must explore all possibilities and backtrack such as:

Generating permutations and combinations
Solving constraint satisfaction problems

Disadvantages of Depth First Search

May Not Find the Shortest Path

DFS does not guarantee the shortest path in an unweighted graph. It may return a longer or suboptimal path, unlike BFS.

Can Get Trapped in Cycles

If the graph contains cycles and you don’t keep track of visited nodes, DFS can go into an infinite loop.

Can Go Very Deep

In a deep or infinite graph (or tree), DFS might go too deep, consuming a large amount of stack memory and potentially causing a stack overflow (in recursive versions).

Less Optimal for Wide Graphs

DFS might explore long paths unnecessarily before finding a result. In wide graphs, BFS is more efficient at exploring the nearest nodes first.

Not Always Complete

In infinite graphs (or trees), DFS may never terminate if the goal is unreachable and the search space is infinite.

Menu