Graph Traversal: Depth First Search (DFS)

Definition

Depth First Search (DFS) is a traversal algorithm for graphs and trees that visits a node first, then recursively explores one of its unvisited neighbors deeply until no more unvisited vertices remain, after which it backtracks to explore other branches.

In simple terms, DFS follows a “go deep first, then return” strategy. It can be implemented using:

Recursion

, where the program call stack keeps track of the path

Stack

, an explicit data structure used to simulate recursion

DFS can be applied to:

Directed graphs

Undirected graphs

Connected or disconnected graphs

Trees

, which are special kinds of graphs

Main Content

1. DFS Traversal Strategy

Depth-first approach

DFS moves from the current vertex to one of its unvisited adjacent vertices and continues moving deeper until it cannot proceed further. Only then does it backtrack.

Backtracking behavior

When a vertex has no unvisited neighbor left, DFS returns to the previous vertex and checks other possible paths.

Example

Consider the graph:

      A
     / \
    B   C
   / \   \
  D   E   F

If DFS starts from A, one possible traversal order is: A -> B -> D -> E -> C -> F

The exact order may vary depending on how neighbors are stored or selected, but the principle remains the same: go deep before exploring sideways.

Comparison with BFS

Unlike Breadth First Search (BFS), which explores level by level, DFS explores a path as far as possible before moving to another branch.

2. DFS Implementation Methods

Recursive implementation

DFS is often written using recursion. Each recursive call processes one vertex and then calls DFS for its unvisited neighbors. This is the most natural implementation for trees and graphs.

Basic recursive idea:

Visit the current vertex
Mark it as visited
For each adjacent vertex, if it is unvisited, call DFS on it

Iterative implementation using stack

DFS can also be implemented without recursion by using an explicit stack. This is useful when recursion depth may become too large.

Visited tracking

A visited array/set is used to prevent revisiting vertices and getting stuck in cycles. For example, in a graph with a cycle, without visited tracking, DFS could loop forever.

Pseudocode idea

  DFS(v):
      mark v as visited
      for each neighbor u of v:
          if u is not visited:
              DFS(u)

3. DFS Applications and Graph Properties

Cycle detection

DFS helps detect cycles in both directed and undirected graphs. In directed graphs, special tracking of recursion stack or color states is used. In undirected graphs, revisiting a visited node other than the parent may indicate a cycle.

Path finding and connectivity

DFS can be used to check whether a path exists between two vertices and to determine whether a graph is connected. If all vertices are reachable from a start node, the graph is connected.

Component discovery and advanced uses

DFS is used to find connected components, topological sorting in directed acyclic graphs (DAGs), articulation points, bridges, and strongly connected components.

Example use case

In a social network graph, DFS can be used to explore all friends connected indirectly to a person, one chain at a time, until the entire connected region is covered.

Working / Process

1. Choose a starting vertex

Select any vertex in the graph as the start point.
Mark it as visited so that it is not processed again.
Add it to the traversal path/output.

2. Visit an unvisited neighbor deeply

From the current vertex, look for an adjacent vertex that has not yet been visited.
Move to that neighbor immediately.
Repeat the same process from that new vertex.

3. Backtrack when no unvisited neighbors remain

If the current vertex has no unvisited adjacent vertices, go back to the previous vertex.
Continue exploring remaining unvisited neighbors there.
Stop when all reachable vertices from the start vertex have been visited.

Example Walkthrough

Consider the graph:

If DFS starts from 1 and chooses the left branch first:

Visit 1
Go to 2
Go to 4
4 has no unvisited neighbor, so backtrack to 2
Visit 5
Backtrack to 1
Visit 3
Visit 6

Traversal order: 1 -> 2 -> 4 -> 5 -> 3 -> 6

DFS and Disconnected Graphs

If the graph is disconnected, DFS from one starting vertex will only visit its connected part. To visit all vertices, repeat DFS from every unvisited vertex:

Start DFS from the first unvisited node
After it finishes, search for another unvisited node
Start DFS again from that node
Continue until every vertex has been visited

This is important for discovering all connected components in a graph.

DFS Complexity

Time complexity

O(V + E)
V = number of vertices
E = number of edges
Each vertex is visited once, and each edge is checked a limited number of times

Space complexity

O(V)
Used by the visited array and recursion stack or explicit stack

ASCII Diagram for DFS Flow

Start at A
   |
   v
Visit A -> go to one unvisited neighbor
   |
   v
Visit B -> go deeper
   |
   v
Visit D -> no more unvisited neighbors
   |
   v
Backtrack to B -> explore next neighbor E
   |
   v
Backtrack to A -> explore next neighbor C

This shows the core DFS idea: progress deeply first, then return and continue.

Advantages / Applications

Efficient graph exploration

DFS is simple, systematic, and efficient for exploring all vertices and edges reachable from a source.

Useful for many graph algorithms

It forms the foundation for cycle detection, topological sorting, connected components, bridge finding, articulation points, and strongly connected components.

Memory-friendly in sparse exploration

DFS can be very practical when the graph is large but only a portion needs to be explored, especially when implemented recursively or with a stack.

Applications in real systems

DFS is used in maze solving, file system traversal, dependency analysis, network exploration, compiler design, and puzzle solving.

Summary

DFS explores a graph by going deep along one path before backtracking.
It can be implemented using recursion or a stack with a visited structure.
DFS is widely used for traversal, cycle detection, connectivity checking, and other graph problems.
Important terms to remember: DFS, visited array, recursion, stack, backtracking, connected component