Depth First Search (DFS) Explained

Depth First Search (DFS) is a graph traversal technique that explores a graph by going as deep as possible along one path before backtracking. Think of it like navigating a maze: you pick one direction and keep moving forward until you hit a dead end. When you cannot move further, you step back to the previous point and try a different path.

DFS begins from a starting node, visits one of its neighbors, then moves to a neighbor of that neighbor, and continues in this deep-down manner until it reaches a node with no unvisited neighbors. To keep track of where to return, DFS uses a stack (or the call stack when recursion is used). This ensures all nodes are eventually explored.

DFS is commonly used for tasks like finding paths, detecting cycles, topological sorting, and exploring all possible states in puzzles or game trees.

Quescol 1-Minute Read

Depth First Search (DFS) is a graph traversal algorithm that explores nodes by going as deep as possible along each path before backtracking. It starts from a selected node, visits one of its neighbors, and continues moving deeper through connected nodes until it reaches a point where no unvisited neighbors remain. Then, it goes back (backtracks) to explore other unvisited paths.

DFS uses a stack (either explicitly or through recursion) to keep track of the traversal path. It is widely used for solving problems like path finding, cycle detection, topological sorting, and backtracking-based puzzles such as Sudoku or the n-Queens problem. DFS helps explore all possible paths in a structured and complete way, ensuring no vertex is missed during traversal.

Key Points about DFS

• Traversal Method: Explores as deep as possible before backtracking to previous nodes.
• Data Structure Used: Implemented using a stack or recursion.
• Exploration Style: Goes deep along one branch before exploring others.
• Path Finding: Useful for finding paths between nodes in a maze or network.
• Cycle Detection: Can detect loops in directed or undirected graphs.
• Topological Sorting: Orders tasks in Directed Acyclic Graphs (DAGs) where dependencies exist.
• Connected Components: Helps identify all connected parts of a graph.
• Backtracking Problems: Solves puzzles like Sudoku, n-Queens, and permutation generation.
• Maze and Puzzle Solving: Explores all possible paths systematically.
• Critical Node Detection: Finds articulation points and bridges in a network.
• Time Complexity:
  • Search → O(V + E)
  • Insertion → O(V + E)
  • Deletion → O(V + E)
• Space Complexity:
  • All Cases → O(V)

Let’s Understand in Depth

What is DFS?

Depth First Search (DFS) is a graph traversal algorithm that explores a graph by moving as deep as possible along each path before backtracking. Starting from a chosen node, DFS visits one of its neighbors, then a neighbor of that neighbor, and continues this way until it reaches a node with no unvisited neighbors. At this point, it backtracks to the previous nodes to explore remaining unexplored paths.

DFS can be implemented using a stack (explicitly) or recursion (implicitly using the call stack). It is widely used for tasks such as finding paths, detecting cycles, topological sorting, and exploring all possible solutions in graphs, trees, and search problems.

Problems That Can Be Solved Using DFS

1. Path Finding – DFS can be used to find a path between two nodes in a graph or maze. It goes deep along each branch until it reaches the destination or a dead end.
2. Cycle Detection – DFS can detect cycles in a graph by keeping track of visited nodes and recursion stack. This is useful in dependency checking or network analysis.
3. Topological Sorting – In directed acyclic graphs (DAGs), DFS is used to arrange nodes in linear order such that every directed edge goes from an earlier node to a later node.
4. Connected Components – DFS helps find all connected parts in a graph. It visits all nodes in one component before moving to the next.
5. Maze and Puzzle Solving – DFS can explore all possible paths in a maze, puzzle, or game to find a solution, sometimes exploring deeper solutions first.
6. Backtracking Problems – DFS is essential for problems like n-Queens, Sudoku, or generating all combinations/permutations, where it explores possibilities recursively and backtracks when stuck.
7. Articulation Points and Bridges – DFS helps find critical nodes or edges in a network whose removal disconnects the graph.

Steps to implement DFS traversal

Steps to implement Depth First Traversal

• Step 1 – Visit all adjacent unvisited vertex. Mark it as visited. Print it and Push it in a stack.
• Step 2 − If no adjacent vertex is found, pop up a vertex from the stack.
• Step 3 − Repeat Step 1 and Step 2 until the stack is empty.

Example Of DFS Graph Traversal

Initialize the stack

Mark 12 as visited and push into stack. Now Explore any unvisited adjacent node from 12. In our example We have three nodes. We can pick any of them. Here we are going to pick 5.

Mark 5 as visited and put it onto the stack. Explore any unvisited adjacent node from 5. Both 12 and 25 are adjacent to 5 but we are concerned for unvisited nodes only.

Visit 25 and mark it as visited and put onto the stack. Here, we have 23 and 3 nodes, which are adjacent to 25 and both are unvisited.

We choose 3, mark it as visited and put onto the stack. Here 3 does not have any unvisited adjacent node. So, we pop 3 from the stack.

We check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find 25 to be on the top of the stack.

Only unvisited adjacent node is from D is 23 now. So we visit 23, mark it as visited and put it onto the stack.

Output of DFS Traversal will be : 3, 23, 25, 5, 12

Pseudocode of DFS

DFS(node, visited):
    mark node as visited
    process(node)

    for each neighbor in adjacency_list[node]:
        if neighbor is not visited:
            DFS(neighbor, visited)

DFS Implementation Using Java

import java.util.*;

public class DFSExample {

    // DFS function
    public static void dfs(Map<String, List<String>> graph, String node, Set<String> visited) {

        if (visited.contains(node)) {
            return;
        }

        visited.add(node);
        System.out.print(node + " ");

        for (String neighbor : graph.get(node)) {
            dfs(graph, neighbor, visited);
        }
    }

    public static void main(String[] args) {

        // Creating the graph
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("D", "E"));
        graph.put("C", Arrays.asList("F"));
        graph.put("D", Collections.emptyList());
        graph.put("E", Collections.emptyList());
        graph.put("F", Collections.emptyList());

        Set<String> visited = new HashSet<>();

        System.out.println("DFS Traversal:");
        dfs(graph, "A", visited);
    }
}

Output

DFS Traversal:
A B D E C F

DFS Traversal Orders: Pre-order, In-order, and Post-order

1. Pre-order Traversal (Root → Left → Right)

You visit the node first, before its children.

• Visit the node
• Go to the left child
• Then go to the right child

You process the root before exploring any subtree.

Example Use: Copying a tree, prefix expressions.

2. In-order Traversal (Left → Root → Right)

You visit the node in between visiting the left and right children.

• Explore left child
• Visit the node
• Explore right child

Used mostly in Binary Search Trees (BSTs) because it gives sorted order.

3. Post-order Traversal (Left → Right → Root)

You visit the node last, after processing all children.

• Visit left child
• Visit right child
• Visit the node

Useful when deleting or evaluating expressions.

Time Complexity of DFS

DFS visits every vertex and every edge exactly once in a graph.

Case	Time Complexity
Best Case, Average Case, Worst Case	O(V + E)

Here:

• V = number of vertices
• E = number of edges

Space Complexity of DFS

DFS uses a visited array + recursion stack/explicit stack, which in the worst case can store all vertices.

Case	Space Complexity
Best Case, Average Case, Worst Case	O(V)

Application of DFS

1. Path Finding
   • DFS can find a path between two nodes in a graph or maze.
   • Example: Navigating a maze or network.
   • How: Explores one path deeply until a dead end, then backtracks to try other paths.
2. Cycle Detection
   • DFS can detect cycles in a graph.
   • Example: Checking for circular dependencies in software tasks.
   • How: Tracks visited nodes and recursion stack to see if a node repeats in the same path.
3. Topological Sorting
   • DFS helps arrange nodes in linear order for directed acyclic graphs (DAGs).
   • Example: Scheduling tasks where some tasks must happen before others.
   • How: Visits nodes and records finish times to create a valid task order.
4. Connected Components
   • DFS identifies all connected parts of a graph.
   • Example: Finding clusters in social networks or computer networks.
   • How: Visits all nodes in one component before moving to the next.
5. Maze and Puzzle Solving
   • DFS explores all possible paths to find a solution.
   • Example: Sliding puzzles, Sudoku, or labyrinths.
   • How: Goes deep along paths and backtracks when hitting dead ends.
6. Backtracking Problems
   • DFS is used in trial-and-error problems requiring backtracking.
   • Example: n-Queens problem, generating permutations or combinations.
   • How: Explores possibilities recursively and backtracks on invalid choices.
7. Articulation Points and Bridges
   • DFS finds critical nodes or edges whose removal disconnects the graph.
   • Example: Important routers or servers in a network.
   • How: Tracks discovery and low times of nodes to detect crucial points.

Conclusion

Depth First Search (DFS) is a way to go through all the points (vertices) of a graph by going as deep as possible along one path before coming back and checking other paths. It visits every vertex without repeating and is useful for finding paths, checking for cycles, and solving many graph problems. DFS is simple, easy to use, and very helpful in understanding and exploring graphs.