Depth First Search (DFS) is a graph traversal algorithm that explores nodes as deep as possible before backtracking. It uses a stack (or recursion) to visit nodes.

Key Points (Quick Revision)

• DFS goes deep first, then backtracks
• Uses Stack (LIFO) or recursion
• Does NOT guarantee shortest path
• Time Complexity: O(V + E)
• Space Complexity: O(V)

DFS in Very Simple Words

DFS means:

• Go as far as possible in one direction
• When stuck → go back
• Then explore the next path

It works like exploring a maze.

Real-Life Example

Imagine:

• You are inside a maze
• You keep moving forward
• If you hit a wall → go back
• Try another path

This is exactly how DFS works.

Example Graph

    0
   / \
  1   2
 / \
3   4

DFS Traversal:

0 → 1 → 3 → 4 → 2

How DFS Works (Step-by-Step)

1. Start from a node
2. Mark it as visited
3. Visit one neighbor
4. Keep going deeper
5. If no path → backtrack
6. Repeat

Algorithm (Simple Version)

Start node
→ Mark visited
→ For each neighbor:
   - If not visited:
      → Call DFS again

Java Code – DFS using Recursion

import java.util.*;

public class DFSGraph {

    int vertices;
    LinkedList<Integer>[] list;

    public DFSGraph(int v) {
        vertices = v;
        list = new LinkedList[v];

        for (int i = 0; i < v; i++) {
            list[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        list[source].add(destination);
        list[destination].add(source);
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        dfsHelper(start, visited);
    }

    private void dfsHelper(int node, boolean[] visited) {

        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : list[node]) {
            if (!visited[neighbor]) {
                dfsHelper(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {

        DFSGraph g = new DFSGraph(5);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);

        System.out.print("DFS Traversal: ");
        g.dfs(0);
    }
}

When to Use DFS

Use DFS when:

• You need to explore all paths deeply
• You are solving maze problems
• You want to detect cycles
• You need topological sorting
• You are working with backtracking problems

Applications of DFS

• Maze solving
• Cycle detection
• Topological sorting
• Path finding
• AI decision making
• Puzzle solving

DFS vs BFS (Simple Difference)

FAQ – Questions & Answers

What is DFS in Data Structures?

DFS is a graph traversal algorithm that explores nodes deeply before backtracking.

Which data structure is used in DFS?

Stack (or recursion) is used in DFS.

What is DFS used for?

DFS is used for path finding, cycle detection, and solving maze problems.

What is the time complexity of DFS?

Time Complexity of DFS is O(V + E).