When should I use BFS versus DFS for a traversal problem?

This is the most common crossroads you'll hit. I usually tell people to think about the goal of the traversal. If you're looking for the shortest path—like the fewest number of hops between two people in a social network or the minimum moves to solve a puzzle—BFS (Breadth-First Search) is your only real option. Because it explores layer by layer, the first time you hit your target, you can be certain you found the shortest route.

DFS (Depth-First Search), on the other hand, is a "dive deep" strategy. It's great for things like detecting cycles in a dependency graph or seeing if a path simply exists between two nodes. It's often easier to implement recursively, which makes the code cleaner, but it can lead you down a rabbit hole (literally) far away from your target before it backtracks. If you don't care about the path length, DFS is usually the quicker way to code it.

How do I stop my code from running in circles forever?

Graphs aren't like trees; they can have cycles. If User A follows User B, and User B follows User A, a naive DFS will just bounce between them until you hit a StackOverflowError. You need a way to remember where you've already been.

The industry standard is a Set (usually a HashSet) to track visited nodes. I've seen some people use a boolean[] array if the nodes are indexed as integers, which is slightly faster, but a Set is more flexible. Here is how I usually structure the "visited" check in a DFS:

public void explore(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
    if (visited.contains(node)) return; // Stop the cycle here

    System.out.println("Visiting node: " + node);
    visited.add(node);

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

What's the most flexible way to represent the graph in Java?

You'll see "Adjacency Matrices" (a 2D array) in a lot of academic textbooks, but in real software engineering, we almost always use an "Adjacency List." Why? Because most real-world graphs are "sparse." If you have 10,000 users but each person only follows 50 people, a 10,000x10,000 matrix wastes a massive amount of memory.

I prefer using a Map<T, List<T>>. It allows your nodes to be anything—Integers, Strings, or custom User objects—without needing to map them to array indices first. Here's a quick way to build one:

Map<String, List<String>> network = new HashMap<>();

public void addConnection(String user1, String user2) {
    network.computeIfAbsent(user1, k -> new ArrayList<>()).add(user2);
    network.computeIfAbsent(user2, k -> new ArrayList<>()).add(user1); // For undirected graphs
}

Using computeIfAbsent is a nice Java 8+ trick that saves you from those clunky if (map.get(key) == null) checks.

📋 Practical Task

Exercise: Social Network Degree-of-Separation Finder

You are building a "Degrees of Separation" feature. Given a graph representing a social network (where nodes are people and edges are friendships), write a method int findShortestDistance(String start, String target, Map<String, List<String>> network) that returns the minimum number of hops between two people.

• Use a Breadth-First Search (BFS) approach to ensure the shortest path is found.
• Use a Queue to manage the nodes to visit and a Set to keep track of visited people.
• If the target is unreachable, return -1.
• If the start and target are the same person, return 0.

Test your implementation with a network where: Alice knows Bob, Bob knows Charlie, and Charlie knows David. The distance from Alice to David should be 3.