How do you decide between BFS and DFS - and how do you recognise a graph problem that nobody described as a graph?

The choice is driven by the question being asked

BFS explores in order of increasing distance from the source, so it answers questions phrased in terms of fewest: fewest moves, minimum number of transformations, shortest chain. That guarantee holds only when every edge costs the same. The instant edges carry different weights, the first time BFS reaches a node is no longer the cheapest time, and you need Dijkstra instead - or, if the only weights are 0 and 1, a double-ended queue where zero-cost edges are pushed to the front and unit-cost edges to the back.

DFS answers structural questions. Is the graph connected, does it contain a cycle, what is a valid ordering of these dependencies, does a path exist at all. It commits to one branch and unwinds, which makes it the natural fit for anything where you need to know what a subtree or a component contains before you can answer, because the post-order return point is where that information becomes available.

Memory is the second axis and it is often the deciding one. BFS holds an entire frontier, which for a branching factor b at depth d is O(b^d) nodes in the worst case; on a wide graph the queue is the thing that runs out. DFS holds only the current path, O(depth), which is why it wins on wide-and-shallow and loses on deep-and-narrow, where the recursion stack overflows somewhere in the low hundreds of thousands of frames on a default JVM thread. If you need DFS on a graph that deep, convert it to an explicit stack rather than raising the thread stack size.

Traversal that gets the details right

int fewestMoves(Map<String, List<String>> graph, String start, String goal) {
    Deque<String> queue = new ArrayDeque<>();
    Set<String> seen = new HashSet<>();
    queue.add(start);
    seen.add(start);

    int distance = 0;
    while (!queue.isEmpty()) {
        for (int remaining = queue.size(); remaining > 0; remaining--) {  // snapshot the level size
            String node = queue.poll();
            if (node.equals(goal)) return distance;
            for (String next : graph.getOrDefault(node, List.of())) {
                if (seen.add(next)) queue.add(next);   // add() returns false if already present
            }
        }
        distance++;                                    // one increment per level, not per node
    }
    return -1;
}

Two details carry the correctness. The level size is captured before the inner loop begins, because the loop is appending to the same queue as it drains it; reading queue.size() inside the condition would run away. And seen.add(next) is doing double duty as test-and-mark in one operation, which is idiomatic and hard to get wrong by accident.

DFS is shorter but needs the same discipline about where the mark goes:

void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;                    // mark on entry, before recursing
    for (int next : adj.get(node)) {
        if (!visited[next]) dfs(next, adj, visited);
    }
}

Marking visited at the wrong moment

The single most common defect in a written BFS is marking a node visited when it is dequeued rather than when it is enqueued. The traversal still terminates and still returns the right distance, so it passes the small test case and looks fine. What it does is enqueue the same node once per incoming edge, so the queue holds up to O(E) entries instead of O(V), and on a dense graph the memory and the constant factor both blow up. The check-on-dequeue variant then needs a second visited test at the top of the loop to avoid re-expanding, and candidates who add that test have usually reinvented a broken version of the correct thing.

The mirror-image error in DFS is marking after the recursive call rather than before, which on any graph containing a cycle recurses forever. Both errors come from the same place: treating the visited set as a record of what has been processed rather than as a record of what has been committed to.

Naming the nodes out loud

Interview graph problems are rarely handed over as an adjacency list. They arrive as a grid of cells, a set of word transformations, a lock with four dials, a list of build dependencies, a currency exchange table. The recognition test is mechanical: can you finish the sentence "a node is ___, and there is an edge from A to B when ___". If you can, everything you know about traversal applies, and you never have to build the adjacency structure at all - you generate neighbours on demand, which is what makes a state space of millions of lock combinations tractable.

Two vocabulary cues are worth listening for. "Minimum number of steps" over uniform moves means BFS almost every time. "Order these such that each comes after its prerequisites" means a topological sort, which means a directed graph and a cycle check, because the ordering only exists if the graph is acyclic. A candidate who states the nodes and edges before writing any code has done the part that transfers; the traversal itself is the part you can look up.