DFS vs BFS: Graph Traversal Explained with Examples

1. DFS : Going Deep Before Going Wide

Imagine you are exploring a cave with several tunnels. You enter the first tunnel and keep going as deep as possible until you reach the end or a point where there are no more unexplored tunnels. When you reach a dead end, you go back to the previous point where you had another choice and explore the next tunnel. So, instead of exploring all the nearby tunnels first, you completely explore one path before moving to another. This is exactly how DFS (Depth-First Search) works.

DFS starts from a node and keeps moving to an unvisited neighboring node until it cannot go any further. Then, it goes back to the previous node and continues with another unvisited neighbor. This process continues until all reachable nodes have been visited. The idea of going forward, exploring deeply, and then coming back is also closely related to backtracking. The main difference is that DFS is mainly used to visit or explore nodes, while backtracking usually involves making a choice, exploring it, and undoing that choice when necessary.

A common way to implement DFS is using recursion. Recursion works naturally here because when we move to a neighboring node, the function calls itself and continues going deeper. When there are no more unvisited neighbors, the function returns to the previous call, which automatically gives us the go deep → come back → try another path behavior.

import java.util.*;

public class GraphDFS {
    public static List<Integer> dfs(int start, Map<Integer, List<Integer>> graph) {
        List<Integer> visitOrder = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, graph, visited, visitOrder);
        return visitOrder;
    }

    private static void dfsHelper(int node, Map<Integer, List<Integer>> graph,
                                    Set<Integer> visited, List<Integer> visitOrder) {
        if (visited.contains(node)) {
            return; // already been here, don't go in circles
        }

        visited.add(node);
        visitOrder.add(node);

        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            dfsHelper(neighbor, graph, visited, visitOrder);
        }
    }
}

That visited set is doing something genuinely important and it's worth pausing on why. Real-world graphs, unlike neat family trees, often have cycles person A knows person B, who knows person C, who knows person A again. Without tracking which nodes you've already visited, your code would keep walking around that same little loop forever, never actually finishing. The visited set is your ball of string it's what stops you from wandering back into a tunnel you've already fully explored.

If you'd rather avoid recursion maybe because very deep graphs risk a stack overflow you can write the exact same DFS using your own explicit stack:

public static List<Integer> dfsIterative(int start, Map<Integer, List<Integer>> graph) {
    List<Integer> visitOrder = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited.contains(node)) {
            continue;
        }
        visited.add(node);
        visitOrder.add(node);

        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            stack.push(neighbors.get(i));
        }
    }
    return visitOrder;
}

The stack here is playing the exact same role your call stack was quietly playing in the recursive version it's remembering "what should I get back to once I finish exploring this branch," which is the whole mechanical trick behind depth-first behavior.

2. BFS : Spreading Out Layer by Layer

Now, Imagine dropping a small stone into a calm pond. When the stone hits the water, the ripples spread outward in all directions. The ripple first reaches the points that are closest to where the stone was dropped, then it reaches the points that are a little farther away, and then even farther. BFS (Breadth-First Search) works in a similar way.

Instead of going as deep as possible along one path like DFS, BFS explores the graph level by level. It first visits the starting node, then visits all of its direct neighbors, then all the unvisited neighbors of those nodes, and continues spreading outward. In other words, BFS completely explores one layer before moving to the next layer.

A simple real-life example is finding the shortest number of connections between two people on a social network. First, you would check all of your direct friends, which is layer 1. Then you would check your friends' friends, which is layer 2. After that, you would check the next level, and so on. You don't completely explore one person's entire network before checking the others. This layer-by-layer approach is what makes BFS especially useful when a problem asks for the shortest path or minimum number of steps in an unweighted graph.

BFS uses a queue to keep track of the nodes that need to be explored. A queue follows the First In, First Out (FIFO) principle, meaning the node that enters the queue first is processed first. This naturally gives BFS its layer-by-layer behavior.

import java.util.*;

public class GraphBFS {
    public static List<Integer> bfs(int start, Map<Integer, List<Integer>> graph) {
        List<Integer> visitOrder = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start); // mark as visited the moment it enters the queue
        while (!queue.isEmpty()) {
            int node = queue.poll();
            visitOrder.add(node);
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return visitOrder;
    }
}

Notice, One important difference between the DFS and BFS code is when we mark a node as visited. In BFS, we mark a node as visited as soon as we add it to the queue, rather than waiting until we actually process it. This is important because the same node can be connected to multiple other nodes. If we wait until processing the node to mark it as visited, different neighbors might add the same node to the queue multiple times. This would cause unnecessary work and could lead to incorrect behavior in some situations. By marking the node as visited immediately when it enters the queue, we make sure that each node is added to the queue only once. This is a small detail, but it is an important part of writing a correct and efficient BFS solution.

In simple terms:

BFS: Mark as visited when adding to the queue. Then process it when it comes out of the queue.

DFS = Visit a node → Go deeper → Reach the end → Come back → Try another path.

BFS = Visit the current node → Visit all nearby nodes → Move to the next layer → Repeat.

DFS vs BFS : A Side-by-Side Comparison

A simple rule of thumb I give people: if the question mentions the word "shortest" or "minimum steps," reach for BFS first. If the question is about exploring everything, checking if a path exists at all or building up a partial solution as you go, DFS is usually the more natural fit.

Graph Traversal Examples

Example 1 : Counting Islands (DFS on a Grid)

The problem: You're given a 2D grid of 1s (land) and 0s (water). An island is a group of connected 1s, connected horizontally or vertically. Count how many separate islands exist.

Think of this exactly like looking at a satellite image of a coastline. Every time your eye lands on a new, unexplored patch of land, that's a new island and once you spot it, your eye naturally traces out its entire connected shape before moving on to look for the next one. That "trace out the entire connected shape" step is a perfect real-world description of DFS.

public class NumberOfIslands {
    public static int countIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int islandCount = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    islandCount++;       // found the start of a brand new island
                    exploreIsland(grid, r, c, visited); // trace out its full shape
                }
            }
        }
        return islandCount;
    }

    private static void exploreIsland(char[][] grid, int row, int col, boolean[][] visited) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) {
            return; // walked off the edge of the grid
        }
        if (visited[row][col] || grid[row][col] == '0') {
            return; // already explored or it's water
        }
        visited[row][col] = true;
        exploreIsland(grid, row + 1, col, visited);
        exploreIsland(grid, row - 1, col, visited);
        exploreIsland(grid, row, col + 1, visited);
        exploreIsland(grid, row, col - 1, visited);
    }
}

Every time the outer loop finds an unvisited 1, that's a brand new island and exploreIsland behaves exactly like your eye tracing the coastline it marks every connected piece of land as visited so the outer loop never mistakenly counts it as a second, separate island later on.

Example 2 : Shortest Path in a Maze (BFS)

The problem: Given a graph, find the minimum number of steps needed to get from a starting node to a target node.

This is the single most common real reason BFS gets used in practice think of GPS apps calculating "how many turns to your destination," or a video game character finding the shortest route across a level.

import java.util.*;

public class ShortestPath {
    public static int shortestPath(int start, int target, Map<Integer, List<Integer>> graph) {
        if (start == target) {
            return 0;
        }

        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);
        int steps = 0;
        while (!queue.isEmpty()) {
            int nodesInThisLayer = queue.size();
            steps++; // we're about to explore one layer further out
            for (int i = 0; i < nodesInThisLayer; i++) {
                int node = queue.poll();
                for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                    if (neighbor == target) {
                        return steps; // found it, this is the shortest path length
                    }
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.add(neighbor);
                    }
                }
            }
        }
        return -1; // target is not reachable at all
    }
}

The nodesInThisLayer trick is the one new idea here and it's worth understanding exactly why it's needed. Without it, you'd still visit nodes in the correct overall order, but you'd lose track of exactly which layer you're currently in and knowing that layer number is precisely what tells you the shortest distance. By grabbing the queue's current size before processing anything, you know exactly how many nodes belong to "this layer," process exactly those and only then increase your step count for the next layer.

A quick trace: for a graph with edges 1-2, 1-3, 2-4, 3-4, 4-5, finding the shortest path from 1 to 5: layer 1 explores neighbors of 1, which are 2 and 3 neither is the target, so they get added to the queue. Layer 2 explores neighbors of 2 and 3, both of which lead to 4 not the target yet, added once (the visited check stops it from being added twice). Layer 3 explores neighbors of 4, which includes 5 a match, so it returns 3. That's the correct shortest distance, 1 → 2 → 4 → 5, three steps.

Example 3 : Finding a Cycle (DFS With a Twist)

The problem: Given a directed graph, determine if it contains a cycle a path that loops back to a node you've already visited during the current exploration.

Here's a real-world version of this exact problem: imagine a list of task dependencies at work, like "finish task A before starting task B." If task A depends on task B and task B somehow also depends on task A, you're stuck in an impossible loop neither task can ever be started. Detecting this kind of circular dependency is a genuinely common real use of cycle detection and it's exactly the same idea behind tools that check for circular imports in large codebases.

The one new idea here is that a single visited set isn't quite enough you need to separately track which nodes are part of your current exploration path, versus nodes you fully finished exploring a while ago and safely backed out of.

import java.util.*;

public class CycleDetection {
    public static boolean hasCycle(Map<Integer, List<Integer>> graph, int numNodes) {
        boolean[] visited = new boolean[numNodes];
        boolean[] inCurrentPath = new boolean[numNodes];
        for (int node = 0; node < numNodes; node++) {
            if (!visited[node]) {
                if (dfs(node, graph, visited, inCurrentPath)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean dfs(int node, Map<Integer, List<Integer>> graph,
                                 boolean[] visited, boolean[] inCurrentPath) {
        visited[node] = true;
        inCurrentPath[node] = true; // mark this node as "currently being explored"
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (inCurrentPath[neighbor]) {
                return true; // we looped back to something still on our current path   a cycle!
            }
            if (!visited[neighbor] && dfs(neighbor, graph, visited, inCurrentPath)) {
                return true;
            }
        }
        inCurrentPath[node] = false; // done exploring this node, remove it from the current path
        return false;
    }
}

That inCurrentPath[node] = false line at the end should genuinely remind you of "unchoose" from backtracking, because it's doing the exact same job once you're done exploring everything reachable from this node, it's no longer part of your current path, even though it's permanently marked as visited overall. This is a great example of how the ideas in this article, backtracking and DFS are really all cousins of the same core idea, just applied to slightly different situations.

Example 4 : Level Order Traversal of a Tree (BFS)

The problem: Given a binary tree, return its values grouped level by level, top to bottom, left to right.

A tree is really just a special, simpler kind of graph no cycles and every node except the root has exactly one parent. Since we want the results grouped strictly by level, this is a natural fit for BFS's layer-by-layer exploration.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class LevelOrderTraversal {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int nodesInThisLevel = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            for (int i = 0; i < nodesInThisLevel; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(currentLevel);
        }
        return result;
    }
}

This is the same nodesInThisLevel trick from the shortest path example, just used to group results together instead of counting steps. Once you've internalized this trick once, you'll recognize it instantly in every "process things layer by layer" problem you come across afterward.

When Should You Use DFS and When Should You Use BFS?

Here's a practical, no-nonsense way to decide, the same way I'd talk through it with someone I was mentoring:

• Need the shortest path or minimum number of steps in an unweighted graph? Use BFS. Its layer-by-layer nature guarantees the first time you reach a node, you've reached it by the shortest possible route.
• Need to check if a path exists at all, without caring how long it is? Either works, but DFS is usually simpler to write, especially with recursion.
• Need to explore every possible combination, arrangement or solution? DFS, almost always this is the backtracking territory from the previous article.
• Working with a very deep, narrow graph (like a long chain)? Be cautious with recursive DFS, since deep recursion can hit a stack overflow either use the iterative version with your own stack or lean toward BFS instead.
• Working with a very wide graph (like a node connected to thousands of others)? Be mindful that BFS might hold a very large number of nodes in its queue at once, using more memory than DFS would at that same point.
• Detecting cycles or dependencies (like our task-scheduling example)? DFS, using the visited plus inCurrentPath combination.

1. Is a tree a type of graph?

Yes a tree is simply a graph with no cycles, where every node (except the root) has exactly one parent.

2. Do I always need a visited set?

Almost always, yes, unless you're absolutely certain the graph has no cycles and no way to reach the same node twice, like a simple tree.

3. Which one is easier to code, DFS or BFS?

Recursive DFS is usually the shortest to write, since recursion naturally handles the "go deep, then come back" behavior for you. BFS requires a bit more setup with a queue, but it's still very manageable once you've written it a few times.

4. Can DFS find the shortest path too?

Not reliably. DFS might stumble onto the shortest path by luck, but it has no built-in guarantee of it, since it doesn't explore layer by layer the way BFS does. This is exactly the mistake I made in the "people you may know" story above DFS found a connection, just not the closest one.

5. What happens if I run DFS or BFS on a graph with no edges at all?

It simply visits the starting node and stops immediately, since there are no neighbors to explore completely valid, just a very short traversal.

6. Why does BFS use a queue and DFS use a stack?

Because a queue processes things in the same order they were added (first in, first out), which matches exploring layer by layer. A stack processes the most recently added thing first (last in, first out), which matches diving deep into whatever you just discovered before backing out.

7. Is recursion always safe for DFS?

Not for extremely deep graphs, since each recursive call uses a bit of memory on the call stack and a very long chain of nodes can eventually cause a stack overflow. The iterative version using your own stack avoids this risk entirely.

8. How is cycle detection different in directed versus undirected graphs?

In directed graphs, you need the inCurrentPath tracker from Section 8, since simply revisiting a node isn't automatically a cycle. In undirected graphs, it's usually simpler you just need to make sure you don't count "going back the way you came" as a false cycle.

9. What's a real, non-coding example of BFS I'd already understand?

Contact tracing during an outbreak is a great one health officials first check everyone who had direct contact with a sick person (layer 1), then everyone those people had contact with (layer 2), spreading outward in exactly the same layer-by-layer way BFS does.

10. Do DFS and BFS work the same way on weighted graphs?

They can still visit every node correctly, but neither one accounts for different edge costs for that, you'd move on to something like Dijkstra's algorithm, which is really BFS's more sophisticated cousin, built specifically to handle weights properly.

11. Which one should I learn first, DFS or BFS?

Either order works, but most people find DFS slightly more intuitive to start with, since recursion often feels more natural than manually managing a queue. Learn one solidly, then use the comparison table in Section 5 to see how the other one differs.

How to Identify and Approach Backtracking Problems

How to Identify and Approach Dynamic Programming Questions

How to Approach Any DSA Interview Problem: Complete Step-by-Step Guide

Sliding Window Patterns in DSA

Real Interview Experiences: Google, Amazon and Meta

The Ultimate Interview Practice Sheet for FAANG Interviews