# Graph BFS and DFS Interview Patterns: Islands, Shortest Path, Cycle Detection

Source: https://www.techinterview.org/post/3233463119/graph-bfs-dfs-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## Graph BFS and DFS Interview Patterns

Graph traversal is one of the most tested interview topics. BFS (Breadth-First Search) and DFS (Depth-First Search) are the two fundamental algorithms — all other graph algorithms build on them. The key skill: recognize which traversal is appropriate and handle visited state correctly.

- [Coinbase Interview Guide](https://techinterview.org/coinbase-software-engineer-interview/)

- [Databricks Interview Guide](https://techinterview.org/databricks-interview-guide/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)

## BFS Template


```
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        process(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
```

BFS explores level by level — all nodes at distance 1, then distance 2, etc. This guarantees shortest path in unweighted graphs. Time: O(V+E). Space: O(V) for the queue.

## DFS Template (Iterative and Recursive)


```
# Recursive DFS
def dfs(graph, node, visited):
    visited.add(node)
    process(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Iterative DFS (avoids recursion limit)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        process(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
```


## Pattern 1: Number of Islands (Grid BFS/DFS)


```
def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        if r = rows or c = cols or grid[r][c] != '1': return
        grid[r][c] = '0'  # mark visited by sinking
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r+dr, c+dc)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count
```


## Pattern 2: Shortest Path in Grid (BFS)


```
def shortest_path(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
    visited = {(start[0], start[1])}
    while queue:
        r, c, dist = queue.popleft()
        if (r, c) == (end[0], end[1]): return dist
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==0 and (nr,nc) not in visited:
                visited.add((nr,nc))
                queue.append((nr,nc,dist+1))
    return -1  # no path
```

BFS guarantees shortest path for unit-weight edges. Add distance to queue state — do not track distances separately.

## Pattern 3: Course Schedule (Cycle Detection with DFS)


```
def can_finish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites: graph[b].append(a)
    # 0=unvisited, 1=in progress, 2=done
    state = [0] * numCourses
    def dfs(node):
        if state[node] == 1: return False  # cycle
        if state[node] == 2: return True   # already processed
        state[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor): return False
        state[node] = 2
        return True
    return all(dfs(i) for i in range(numCourses))
```

Three-color DFS: unvisited (0), in-progress/gray (1), done/black (2). A back edge to a gray node = cycle.

## Pattern 4: Multi-Source BFS


```
# "01 Matrix": distance to nearest 0 for each cell
def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[float('inf')]*cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))    # seed ALL zeros simultaneously
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r+dr, c+dc
            if 0<=nr<rows and 0<=nc dist[r][c]+1:
                dist[nr][nc] = dist[r][c]+1
                queue.append((nr,nc))
    return dist
```

Add ALL source nodes to the queue before starting BFS. The wave expands simultaneously from all sources. Equivalent to adding a virtual source node connected to all real sources.

## BFS vs DFS: When to Use Which

  - BFS: shortest path in unweighted graph, level-order traversal, minimum steps

  - DFS: cycle detection, topological sort, connected components, maze solving (any path)

  - Both work: number of islands, number of connected components

🏢 Asked at: [Atlassian Interview Guide](https://techinterview.org/atlassian-interview-guide/)