Graph Search & Pathfinding

What is a graph?

A graph is a collection of nodes (sometimes called vertices) connected by edges. That's it. If you can model something as "things" and "connections between things," you've got a graph.

There are two standard ways to represent a graph in code, and you should know both because the AI will ask (or assume) one or the other.

Adjacency list. Each node stores a list of its neighbors. This is the default for most interview problems because it's memory-efficient for sparse graphs, which covers most real-world graphs and keeps test cases with large graphs from requiring huge binaries.

import java.util.*;

Map<String, List<String>> graph = new HashMap<>() {{
    put("A", List.of("B", "D"));
    put("B", List.of("A", "C", "D", "E"));
    put("C", List.of("B", "E"));
    put("D", List.of("A", "B", "E", "F"));
    put("E", List.of("B", "C", "D", "F"));
    put("F", List.of("D", "E"));
}};

Adjacency matrix. A 2D grid where matrix[i][j] = 1 means there's an edge from node i to node j. This is better for dense graphs or when you need O(1) edge lookups, but uses memory.

//       A  B  C  D  E  F
int[][] matrix = {
    {0, 1, 0, 1, 0, 0},  // A
    {1, 0, 1, 1, 1, 0},  // B
    {0, 1, 0, 0, 1, 0},  // C
    {1, 1, 0, 0, 1, 1},  // D
    {0, 1, 1, 1, 0, 1},  // E
    {0, 0, 0, 1, 1, 0},  // F
};

In practice, you'll almost always use adjacency lists. If the AI generates a matrix representation and the graph is sparse, that's a red flag worth catching.

Graph traversal algorithms

Four algorithms cover almost everything you'll see: BFS and DFS for unweighted graphs, Dijkstra's for weighted graphs, and A* when you have a way to estimate distance to the goal. The right pick falls out of the problem shape, so it's worth knowing what each one buys you.

BFS: Breadth-First Search

BFS explores a graph level by level. It visits all neighbors of the starting node first, then all neighbors of those neighbors, and so on. Think of it like dropping a stone in a pond: the ripple expands outward uniformly.

This property makes BFS the go-to algorithm for finding the shortest path in an unweighted graph. Because it explores nodes in order of their distance from the start, the first time it reaches any node is guaranteed to be via the shortest path.

Starting from the root, BFS pulls one node off the queue, marks it visited, and pushes its unvisited neighbors to the back. Nodes finish in level order: depth-1 before depth-2, depth-2 before depth-3.

import java.util.*;

public static List<String> bfs(Map<String, List<String>> graph, String start, String target) {
    Queue<Map.Entry<String, List<String>>> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    queue.add(Map.entry(start, List.of(start)));
    visited.add(start);

    while (!queue.isEmpty()) {
        var entry = queue.poll();
        String node = entry.getKey();
        List<String> path = entry.getValue();

        if (node.equals(target)) {
            return path;
        }

        for (String neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                List<String> newPath = new ArrayList<>(path);
                newPath.add(neighbor);
                queue.add(Map.entry(neighbor, newPath));
            }
        }
    }

    return null;
}

The key data structure is the queue (FIFO). Nodes go in at the back and come out at the front, which enforces the level-by-level ordering. The visited set prevents cycles from causing infinite loops.

When to use BFS:

• Shortest path in an unweighted graph
• Level-order traversal (e.g., "find all nodes within K hops")
• Any problem that asks for the minimum number of steps

DFS: Depth-First Search

DFS takes the opposite approach. Instead of exploring broadly, it goes as deep as possible down one path before backtracking. It's like exploring a maze by always taking the first turn you see and only backing up when you hit a dead end.

import java.util.*;

public static List<String> dfs(Map<String, List<String>> graph, String start, String target, Set<String> visited) {
    if (visited == null) {
        visited = new HashSet<>();
    }

    visited.add(start);
    if (start.equals(target)) {
        return new ArrayList<>(List.of(start));
    }

    for (String neighbor : graph.get(start)) {
        if (!visited.contains(neighbor)) {
            List<String> result = dfs(graph, neighbor, target, visited);
            if (result != null) {
                result.add(0, start);
                return result;
            }
        }
    }

    return null;
}

You can also write DFS iteratively with an explicit stack, which avoids recursion depth limits for large graphs:

import java.util.*;

public static List<String> dfsIterative(Map<String, List<String>> graph, String start, String target) {
    Deque<Map.Entry<String, List<String>>> stack = new ArrayDeque<>();
    Set<String> visited = new HashSet<>();

    stack.push(Map.entry(start, List.of(start)));

    while (!stack.isEmpty()) {
        var entry = stack.pop();
        String node = entry.getKey();
        List<String> path = entry.getValue();

        if (node.equals(target)) {
            return path;
        }

        if (visited.contains(node)) {
            continue;
        }
        visited.add(node);

        for (String neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                List<String> newPath = new ArrayList<>(path);
                newPath.add(neighbor);
                stack.push(Map.entry(neighbor, newPath));
            }
        }
    }

    return null;
}

DFS doesn't guarantee shortest paths. The path it finds depends entirely on the order it explores neighbors. So why use it?

When to use DFS:

• Cycle detection. As DFS walks down a path, it can mark nodes as "currently on the stack." Bumping into one of those again means you've looped back, which is a cycle.
• Topological sorting (see the topological sort article). Finishing order from DFS naturally produces a valid ordering of nodes that respects dependencies.
• Finding any path (not necessarily shortest). When you just need a solution, going deep is often faster than expanding the whole frontier level by level.
• Exploring all possible paths (e.g., maze solving, backtracking problems). DFS pairs naturally with the choose/explore/unchoose rhythm because the recursion stack already tracks where to back up to.
• Connected component detection. Start DFS from each unvisited node; everything you touch is one component. Repeat until every node has been seen.
• Problems with deep recursive structure. If the problem itself is recursive (trees, nested expressions, fractal-like state), DFS's recursion mirrors the structure for free.

DFS uses less memory than BFS in practice. BFS has to store the entire frontier (which can be huge for wide graphs), while DFS only stores the current path. For very large graphs, this matters.

Weighted graphs and Dijkstra's algorithm

So far we've assumed every edge has the same weight. Real problems often don't work that way. In a road network, different roads have different distances. In a network, different links have different latencies. When edges have weights, BFS no longer gives you the shortest path; it gives you the path with the fewest edges, not the lowest total weight.

Enter Dijkstra's algorithm. It's essentially BFS, but instead of a regular queue, it uses a priority queue (min-heap) that always processes the node with the smallest known distance first. This guarantees that when you reach a node, you've found the cheapest path to it.

import java.util.*;

public static Map.Entry<Integer, List<String>> dijkstra(
    Map<String, List<Map.Entry<String, Integer>>> graph, String start, String target
) {
    record State(int cost, String node, List<String> path) {}

    PriorityQueue<State> heap = new PriorityQueue<>(Comparator.comparingInt(s -> s.cost));
    Set<String> visited = new HashSet<>();

    heap.add(new State(0, start, List.of(start)));

    while (!heap.isEmpty()) {
        State current = heap.poll();

        if (current.node.equals(target)) {
            return Map.entry(current.cost, current.path);
        }

        if (visited.contains(current.node)) {
            continue;
        }
        visited.add(current.node);

        for (var edge : graph.get(current.node)) {
            String neighbor = edge.getKey();
            int weight = edge.getValue();
            if (!visited.contains(neighbor)) {
                List<String> newPath = new ArrayList<>(current.path);
                newPath.add(neighbor);
                heap.add(new State(current.cost + weight, neighbor, newPath));
            }
        }
    }

    return Map.entry(Integer.MAX_VALUE, null);
}

The graph representation changes slightly for weighted graphs. Instead of a list of neighbors, each entry is a tuple of (neighbor, weight):

import java.util.*;

Map<String, List<Map.Entry<String, Integer>>> graph = new HashMap<>() {{
    put("A", List.of(Map.entry("B", 4), Map.entry("D", 2)));
    put("B", List.of(Map.entry("A", 4), Map.entry("C", 3), Map.entry("D", 1)));
    put("C", List.of(Map.entry("B", 3), Map.entry("E", 6)));
    put("D", List.of(Map.entry("A", 2), Map.entry("B", 1), Map.entry("E", 5), Map.entry("F", 3)));
    put("E", List.of(Map.entry("C", 6), Map.entry("D", 5), Map.entry("F", 2)));
    put("F", List.of(Map.entry("D", 3), Map.entry("E", 2)));
}};

In this graph, the shortest path from A to C isn't the direct A-B-C route (cost 7). It's A-D-B-C (cost 6), because the detour through D is cheaper. Dijkstra's finds this automatically.

A*: Dijkstra's with a heuristic

A* is Dijkstra's smarter cousin. The insight for it is pretty simple: if you have some idea of which direction the target is in, you can prioritize nodes that seem closer to the goal. Instead of sorting the heap by cost_so_far, A* sorts by cost_so_far + estimated_cost_to_goal.

That estimated cost is the heuristic function, often called h(n). For grid-based pathfinding, Manhattan distance or Euclidean distance are common choices. As a concrete example: if you're at grid cell (2, 3) and the goal is (5, 7), the Manhattan distance is |5-2| + |7-3| = 7. You don't actually know if there's a clear path that short (there could be walls), but you know any real path has to be at least that long. That's the property A* uses to decide which frontier node to expand next.

The heuristic has to be admissible: it can never overestimate the actual cost. If it does, A* might rule out the optimal path before ever exploring it. Manhattan distance is admissible on a 4-directional grid because the real path can never be shorter than walking straight to the goal.

This basically means A* is most useful in scenarios where there is some structure to the problem that can be used to estimate the cost to the goal like if the problem involves spatial pathfinding (grid navigation, map routing, robot movement). In these cases, A* will be significantly faster than plain Dijkstra's because it avoids exploring nodes in the wrong direction. For abstract graphs without spatial structure, A* degrades to Dijkstra's because there's no useful heuristic.

import java.util.*;
import java.util.function.BiFunction;

public static Map.Entry<Integer, List<String>> astar(
    Map<String, List<Map.Entry<String, Integer>>> graph,
    String start,
    String target,
    BiFunction<String, String, Integer> heuristic
) {
    record State(int priority, int cost, String node, List<String> path) {}

    PriorityQueue<State> heap = new PriorityQueue<>(Comparator.comparingInt(s -> s.priority));
    Set<String> visited = new HashSet<>();

    heap.add(new State(heuristic.apply(start, target), 0, start, List.of(start)));

    while (!heap.isEmpty()) {
        State current = heap.poll();

        if (current.node.equals(target)) {
            return Map.entry(current.cost, current.path);
        }

        if (visited.contains(current.node)) {
            continue;
        }
        visited.add(current.node);

        for (var edge : graph.get(current.node)) {
            String neighbor = edge.getKey();
            int weight = edge.getValue();
            if (!visited.contains(neighbor)) {
                int newCost = current.cost + weight;
                int priority = newCost + heuristic.apply(neighbor, target);
                List<String> newPath = new ArrayList<>(current.path);
                newPath.add(neighbor);
                heap.add(new State(priority, newCost, neighbor, newPath));
            }
        }
    }

    return Map.entry(Integer.MAX_VALUE, null);
}

For a 2D grid where nodes have coordinates:

public static int manhattanDistance(int[] a, int[] b) {
    return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
}

public static double euclideanDistance(int[] a, int[] b) {
    return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));
}

Prompting the AI

The move on graph problems is to tell the interviewer the algorithm and tell the AI the goal. "This is an unweighted shortest path problem, so I'm thinking BFS" is what the interviewer needs to hear. Five seconds, and it demonstrates real understanding. When you prompt the AI, leave a little room: "find the shortest path between these nodes" is better than locking it to BFS, because the AI might suggest something better suited to the specifics, and you want to keep that door open.

A few pattern-specific moves:

• For grid problems, name the reframe. Tell the AI "treat the grid as a graph where each cell connects to its 4 neighbors" rather than asking for a specialized grid traversal. You get a standard BFS/DFS that's easier to read and verify.
• For weighted graphs, confirm the edge weights. "Weights are non-negative, so Dijkstra's works" is a useful sentence to say, both to the interviewer and to the AI. If you skip this and there's a negative edge, Dijkstra's will silently produce a wrong answer.
• For heuristic-based search (A), ask the AI to generate a harness to validate the heuristic.* The AI is much better at writing heuristics than verifying them. A small adversarial test set is a high-leverage prompt.

Verifying the AI's code

Graph algorithms are short and well-known, so the AI usually gets the structure right. The bugs live in a few specific places:

1. BFS that doesn't mark visited on enqueue. Marking visited on dequeue is a classic mistake; you'll add the same node to the queue multiple times and either get an infinite loop or a wrong distance. Check the line where visited.add(node) lives. It should be right after appending to the queue, not after popping from it.
2. Dijkstra's without the "already-visited" skip. A correct implementation pops a node from the heap and immediately checks whether it's been processed; if so, skip. Without this, you re-process nodes and get the wrong distance on graphs with multiple paths to the same node.
3. DFS used for shortest path. If the AI generated DFS for a "minimum steps" problem, that's a structural bug. DFS will time out on anything non-trivial and may not find the shortest path at all.
4. Edge cases the test set didn't surface. Disconnected graphs (target might be unreachable, so does the code return a sentinel or crash?), self-loops, duplicate edges, the graph being a tree (no cycles to handle). The provided test data may not exercise these, but mentioning them out loud tells the interviewer you're thinking past the happy path.

The fastest sanity check: name the data structure. BFS uses a queue, DFS uses a stack (or recursion), Dijkstra's uses a min-heap, A* uses a min-heap sorted by f = g + h. If the AI's code disagrees with what the algorithm name implies, something is wrong before you even read the loop.

When to use vs. alternatives

Graph time complexities are hairy and "bookish"; interviewers don't usually drill on them, but knowing the rough shape helps you flag when a solution will time out. BFS and DFS have the same theoretical complexity, but their memory profiles differ in practice (BFS stores the full frontier; DFS only stores the current path). Dijkstra's and A* have the same worst case, but A* is faster in practice when the heuristic is good.

Neighbor patterns that get confused with graph search:

• Topological sort is graph search restricted to DAGs where the order of traversal is the answer. If the problem is "in what order can these tasks run?", reach for topo sort, not generic graph search.
• Negative-weight shortest paths break Dijkstra's. Use Bellman-Ford instead. If the problem explicitly mentions negative weights (cashback, refunds, currency exchange), don't reach for Dijkstra's.
• Backtracking comes up when the problem is "find all paths" or "enumerate all valid configurations" rather than "find a path." DFS is the engine underneath, but the framing is different.

What interviewers expect

Beyond the recognition step (which is the biggest single signal), interviewers are watching for:

• You can explain the algorithm the AI produced. "It's BFS, but with a tuple of (node, distance) instead of a separate distance map" is the kind of narration that tells the interviewer you understood the choice. If you can't competently explain it, they can't tell whether you got it right or got lucky.
• You proactively name the edge cases. Disconnected graphs, self-loops, duplicate edges, the graph being a tree (no cycles). These may not even appear in the provided test data, but flagging them shows completeness, and they're easier to spot once you've recognized the graph in the first place.
• You frame the algorithm choice as a decision, not a default. "I'm using Dijkstra's because the edges are weighted and non-negative" beats "I'm using Dijkstra's because shortest path." Stating the precondition out loud is the signal.
• You catch the high-leverage bugs. Mark-on-enqueue for BFS, the already-visited skip for Dijkstra's, DFS-for-shortest-path. Naming one of these out loud while reading the AI's code is the kind of thing strong candidates do.

Putting it together

Graph search is one of those patterns where recognition matters far more than implementation. In an AI coding interview, the AI can generate BFS, DFS, or Dijkstra's in seconds. What it can't do is answer the question from the interviewer before hands-on-keyboard to realize that "minimum number of bus transfers to reach a destination" is a BFS problem on a graph where bus routes are nodes.

That insight is yours to bring. Practice spotting graph structure in problems that don't obviously look like graph problems. When you see one, name the algorithm, explain your reasoning to the interviewer, and let the AI handle the boilerplate. Then verify the output against the patterns you know: queues for BFS, stacks for DFS, heaps for Dijkstra's and A*. That's the workflow interviewers want to see.