Graph Interview Bugs: The Ones Your Test Cases Miss

You solved the problem. Your code works on the examples. You trace through it and it looks right. Then in the interview, on a slightly different input, it returns the wrong answer. Or worse, it runs forever.

Graph interview bugs don't announce themselves. They hide in a single misplaced line, or a one-character-off assumption, or a loop you forgot to write. The algorithm is correct. The implementation is a landmine. You only find out when someone steps on it.

Mark Visited on Enqueue, Not on Dequeue

This is the most common BFS bug. It's also the hardest to catch during a live interview, because the code looks completely reasonable.

The buggy pattern:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        visited.add(node)  # BUG: marking on dequeue
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)

Consider a star graph: one center node connected to five outer nodes, all of which are also connected to each other. When you process the center, you enqueue all five neighbors. When you process the first neighbor, nodes two through five are still not in visited (you only mark on dequeue), so you might enqueue the same node multiple times. In a dense graph, you can push the same node O(degree) times. The time complexity quietly degrades from O(V + E) to O(E²). Your solution times out on the large input, and you have no idea why.

The fix is one line earlier:

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)  # mark on enqueue
                queue.append(neighbor)

Mark visited the moment you decide to enqueue. You're saying "I've committed to visiting this node" at that point, not "I've finished visiting it." A node can be discovered by multiple predecessors but should only be queued once. This distinction matters, and you'll feel it when your code goes from O(E²) to O(V + E) on the same problem.

This bug usually passes small test cases because the duplicates don't change the final answer in simple graphs. They just slow things down. In large inputs with high-degree nodes, they cause timeout. That's the worst place to discover a one-line bug.

The Undirected Edge Is Not a Cycle

Cycle detection in undirected graphs has a trap that is genuinely embarrassing when you see it. Every undirected edge is bidirectional: if there's an edge between node A and node B, then when you're at A you see B, and when you're at B you see A. That backward look is not a cycle. It's just an edge. But your code doesn't know that.

The broken approach:

def has_cycle_dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor in visited:
            return True  # BUG: the edge we came from triggers this
        if has_cycle_dfs(graph, neighbor, visited):
            return True
    return False

On a simple two-node graph with one edge, A connected to B: DFS starts at A, marks A visited, recurses to B. From B, it sees A in visited. The code returns True. There is no cycle. The code is confidently, completely wrong.

The fix: track the parent.

def has_cycle_dfs(graph, node, visited, parent=-1):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor == parent:
            continue  # skip the edge we came from
        if neighbor in visited:
            return True
        if has_cycle_dfs(graph, neighbor, visited, node):
            return True
    return False

When you recurse into a neighbor, pass the current node as the parent. At the next level, skip any neighbor that equals the parent. A visited neighbor that is not the parent represents a genuine back edge and a real cycle.

This matters in practice: any problem that builds a tree-like undirected structure (minimum spanning tree validation, graph valid tree) will hit this exact failure. If you forget the parent check, your cycle detector finds cycles that don't exist.

Directed Graphs Need a Recursion Stack, Not Just Visited

Directed graph cycle detection uses completely different logic from undirected, and the two are easy to mix up under pressure.

A simple graph exposes the flaw:

A → C
B → C

No cycle. Now run DFS from A: mark A visited, move to C, mark C visited. Backtrack. Start DFS from B: mark B visited, move to C. C is already in visited. A naive implementation returns "cycle found." Wrong.

The visited set doesn't distinguish between "C was visited in a different DFS path" and "C is an ancestor of the current node." For directed graphs, you only have a cycle if you reach a node that's currently on the active call stack, meaning you've found a path back to your own ancestor.

The correct approach: two arrays.

def has_cycle_directed(graph, node, visited, in_stack):
    visited.add(node)
    in_stack.add(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle_directed(graph, neighbor, visited, in_stack):
                return True
        elif neighbor in in_stack:
            return True  # back edge = real cycle
    
    in_stack.remove(node)  # done with this path
    return False

visited tracks nodes you've ever explored. in_stack tracks nodes on the current active path. When you finish exploring all of a node's descendants, you remove it from in_stack. A node can be visited without being on the current path. That's what visited-only detection misses.

This is the three-color DFS from algorithms textbooks: white (unvisited), gray (in stack), black (done). A gray neighbor means back edge. A black neighbor is fine. The same in_stack logic drives topological sort: if you finish all of a node's descendants and never hit a gray node, it's safe to output in postorder.

The mnemonic: undirected graphs need a parent, directed graphs need a stack. Getting them swapped produces code that looks completely reasonable and fails on carefully constructed inputs. The interviewer will have one.

One BFS Call Doesn't See the Whole Graph

Here's a quiet assumption that breaks a lot of solutions: "the graph is connected."

Most toy examples in interview prep use connected graphs. The algorithms work. You write your BFS or DFS from a single starting node, visit everything reachable, done. Then you get a problem with multiple disconnected components, and your algorithm processes one island and misses the rest entirely. You return the wrong count. You wonder why.

Number of islands is the classic example. If you write:

def count_islands(grid):
    visited = set()
    # start BFS from (0, 0) only -- WRONG
    bfs(grid, 0, 0, visited)
    return 1  # only counted the component containing (0,0)

You've found one component. There might be four more. Your answer is wrong, and it was wrong the moment you wrote the first line.

The fix is an outer loop over all nodes:

def count_islands(grid):
    visited = set()
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1' and (r, c) not in visited:
                bfs(grid, r, c, visited)
                count += 1
    return count

The pattern generalizes: whenever a problem involves counting components, finding the largest component, or reaching any node from any start, you need the outer loop. The guard is always if node not in visited: you only start a new traversal from nodes not yet reached.

Interviewers watch for this. A candidate who asks "can the graph be disconnected?" before writing code signals they know this trap. The question itself is a positive signal in the write-up.

DFS Finds a Path. BFS Finds the Shortest One.

If the problem asks for the minimum number of steps, hops, or edges to reach a destination, reach for BFS. DFS will find some path. It will not necessarily find the shortest one, and making DFS find the shortest path means exploring every possible path, which is O(V!) in the worst case. That's not a typo.

DFS explores as deep as possible before backtracking. The first complete path it finds is just the first one DFS stumbled into, which could be arbitrarily long. BFS explores level by level, so the first time it reaches the destination, it has used the minimum number of edges.

# Wrong: DFS for shortest path
def shortest_path_dfs(graph, start, end):
    def dfs(node, steps):
        if node == end:
            return steps
        visited.add(node)
        min_steps = float('inf')
        for neighbor in graph[node]:
            if neighbor not in visited:
                min_steps = min(min_steps, dfs(neighbor, steps + 1))
        visited.remove(node)  # backtrack
        return min_steps
    
    visited = set()
    return dfs(start, 0)
    # Works but is O(V!) in the worst case. Not what you want.

# Correct: BFS guarantees shortest in O(V + E)
from collections import deque

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

The rule is simple: unweighted graph, minimum edges? BFS. Weighted graph, minimum cost? Dijkstra (or 0-1 BFS if weights are only 0 and 1). DFS is for reachability, cycle detection, topological sort, and exploring all possibilities. Not for shortest paths. The full decision breakdown is in BFS vs DFS: One Question Decides It Every Time.

When you reach for DFS on a shortest-path problem, you've made the problem exponentially harder than it needs to be.

Your State Definition Is Too Narrow

This is the most subtle mistake on the list, and it only shows up in harder problems. It's also the one most likely to look like a correct solution until you hit a specific test case.

Standard BFS tracks which nodes you've visited. That works when the only thing that matters is which node you're at. But some problems have additional state that changes what decisions are valid.

Consider: "minimum moves to reach the exit, but you can pass through at most k walls." Being at cell (2, 3) with 2 wall passes remaining is different from being at (2, 3) with 0 remaining. If your visited set only stores (row, col), you'll mark (2, 3) as visited the first time you reach it and skip it on future visits, even when you arrive with more remaining passes that would allow a shorter path.

# Wrong: visited only tracks position
visited = set()
queue = deque([(start_r, start_c, k, 0)])  # (row, col, walls_left, steps)

while queue:
    r, c, walls, steps = queue.popleft()
    if (r, c) in visited:  # BUG: ignores walls_left
        continue
    visited.add((r, c))
    ...

# Correct: visited tracks the full state
visited = set()
queue = deque([(start_r, start_c, k, 0)])

while queue:
    r, c, walls, steps = queue.popleft()
    if (r, c, walls) in visited:  # full state
        continue
    visited.add((r, c, walls))
    ...

Your visited set must encode everything that affects future decisions. If the same position with different remaining resources should be explored separately, the resource count belongs in the state. This is not optional and not edge-case behavior. It is the algorithm.

This pattern appears in: shortest path with limited fuel, shortest path with key collection (LeetCode 864), word ladder variants, and anything that says "you can do X at most k times."

Dijkstra's Silent Speed Trap

This one doesn't produce wrong answers. It produces slow ones, and in an interview, TLE is a rejection.

Most Dijkstra implementations in Python use heapq. When you find a shorter path to a node, you push a new entry to the heap rather than updating the existing one (because standard heaps don't support decrease-key). This leaves stale entries in the heap. When you pop them, you must check whether they're still valid. The full algorithm with all its edge cases is in Dijkstra's Algorithm.

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    
    while heap:
        d, node = heapq.heappop(heap)
        
        if d > dist[node]:
            continue  # stale entry, skip it
        
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return dist

Without if d > dist[node]: continue, you process every stale heap entry. On a dense graph where many distances get updated, the heap balloons and you process O(E) entries instead of O(V). This check is not optional. It's what keeps Dijkstra at O((V + E) log V) instead of O(E log E).

The same problem reappears in 0-1 BFS. If edges have costs of only 0 or 1, replace the priority queue with a deque: weight-0 neighbors go to the front, weight-1 go to the back. This gives O(V + E) instead of O((V + E) log V). Most candidates pull out Dijkstra for any weighted graph without noticing when edge weights are binary.

Four Questions That Prevent Most Graph Interview Bugs

These bugs have a shape. Most of them are a single missing line or a single wrong location for an existing line.

What makes them dangerous is that they look complete. The structure is there. The traversal happens. The final answer might even be right for every test case you check. The interviewer who has seen these before will ask "what if the graph is disconnected?" or "how would this behave on a directed graph?" and your code will quietly unravel.

The defense is not memorizing fixes. It's building the habit of asking the right questions before you write a single line:

Is the graph directed or undirected?
Can there be disconnected components?
Is shortest path required, or just any path?
What is my state? Is position enough, or do I need more?

Answer those four out loud, and you'll avoid most of what's in this list. Practice explaining those answers under interview pressure at SpaceComplexity, where mock graph interviews come with rubric-based feedback on exactly the things interviewers actually score.