Swe Interview Graph Bfs Dfs Topological Sort

Why Graph Traversal Still Dominates Coding Interviews in 2026

Despite years of predictions that LeetCode-style graph questions would fade in favor of system design and AI-tooling questions, graph traversal — BFS, DFS, and topological sort specifically — remains one of the top three most-asked categories in SWE coding interviews in 2026, according to aggregate data from major interview prep platforms. The reason is structural: graph problems test whether a candidate can correctly reason about state (visited sets), recursion or explicit stack management, and complexity analysis simultaneously, in a way that array/string problems often don’t.

BFS: Level-Order and Shortest Path in Unweighted Graphs

Breadth-first search explores a graph level by level using a queue, visiting all neighbors of the current node before moving to the next depth level. Its defining property, and the reason interviewers ask for it specifically: BFS guarantees the shortest path in an unweighted graph, because the first time you reach a node, you’ve reached it via the minimum number of edges.

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    distance = {start: 0}
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return distance

Time complexity is O(V + E) — every vertex and every edge is visited exactly once. Space complexity is O(V) for the visited set and queue. The most common bug candidates introduce: marking a node visited when it’s dequeued rather than when it’s enqueued. This allows the same node to be added to the queue multiple times via different paths before being processed, which doesn’t break correctness but does break the time complexity guarantee (it degrades toward O(E) redundant enqueues in dense graphs) — interviewers who catch this will ask “what’s your actual time complexity here?” as a follow-up specifically to test whether you notice.

DFS: Recursion, Explicit Stacks, and Cycle Detection

Depth-first search explores as far as possible along one branch before backtracking. It’s implemented either recursively (clean, but risks stack overflow on deep graphs — a real concern for graphs with 10,000+ node chains, which show up in interview follow-ups specifically to test whether you know the recursive approach has this limit) or iteratively with an explicit stack (more code, no recursion depth limit).

DFS’s signature use case beyond simple traversal is cycle detection, which requires tracking three states per node, not two — this is the detail that separates candidates who’ve memorized DFS from those who understand it:

• Unvisited — not yet processed.
• In progress (on the current recursion stack) — currently being explored; if you reach a node in this state again, you’ve found a cycle.
• Fully processed (finished) — done, popped off the recursion stack; revisiting this node is fine and doesn’t indicate a cycle.

A common bug: using only a single visited boolean set (two states, not three) for cycle detection in a directed graph. This works for undirected graphs but produces false positives in directed graphs, because a node can be legitimately reached twice via different, non-cyclic paths as long as neither path revisits it while it’s still on the active recursion stack. This exact bug — conflating “visited” with “currently on the stack” — is one of the most frequently cited failure points in directed-graph cycle detection interview solutions.

Topological Sort: Ordering with Dependencies

Topological sort produces a linear ordering of nodes in a directed acyclic graph (DAG) such that for every directed edge u→v, u appears before v. It’s the canonical solution for dependency resolution problems: build systems, package managers, course prerequisite scheduling, and task scheduling with dependencies — all frequently used as interview problem framing in 2026.

Two standard implementations:

1. Kahn’s algorithm (BFS-based) — compute in-degree for every node, start a queue with all zero-in-degree nodes, repeatedly dequeue a node, add it to the result, and decrement the in-degree of its neighbors, enqueuing any that reach zero. If the result doesn’t contain all nodes at the end, the graph has a cycle (no valid topological order exists) — this cycle-detection-as-a-side-effect is a key insight interviewers look for you to state explicitly.
2. DFS-based — run DFS, and prepend each node to the result list as it finishes (post-order), which naturally produces a valid topological order because a node’s dependencies are always fully processed before the node itself finishes.

Both run in O(V + E). Kahn’s algorithm is generally preferred in production and interview settings because it detects cycles as a natural byproduct of the algorithm terminating early, without needing the separate three-state tracking DFS-based cycle detection requires.

Comparison Table

What Interviewers Actually Grade

The differentiator in graph interviews is rarely “did you get the right final answer” — it’s whether you can state complexity correctly under follow-up pressure, catch your own visited-set bugs before being prompted, and pick the right algorithm for the actual constraint (shortest path → BFS, not DFS; dependency ordering → topological sort, not a naive DFS without cycle handling). Interviewers routinely ask “what if this graph has a cycle” or “what if it’s weighted” as a follow-up specifically to see whether the candidate’s solution was memorized or actually understood.

These exact follow-up patterns, the three-state DFS cycle detection walkthrough, and worked topological sort examples with dependency graphs are covered in The 0-to-1 SWE Interview Playbook — available on Amazon.

FAQ

Q: When should I use BFS instead of DFS? Use BFS whenever you need the shortest path in an unweighted graph, or level-order processing. Use DFS for cycle detection, exhaustive path exploration (backtracking problems), or when memory for a queue at wide graph levels would be prohibitive and recursion depth is manageable.

Q: Can topological sort work on a graph with a cycle? No — topological sort is only defined for DAGs. If a cycle exists, Kahn’s algorithm will terminate with fewer nodes in the result than exist in the graph, which is itself the standard way to detect the cycle programmatically.

Q: Why does my DFS cycle detection give false positives on a directed graph? You’re almost certainly using a single boolean visited set instead of three states (unvisited, in-progress/on-stack, finished). A node reached via two separate paths isn’t a cycle unless it’s revisited while still on the active recursion stack.