Common Graph Problems

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 3 Time to complete: ~30 minutes

Number of Islands
Detect a Cycle in a Directed Graph
Topological Sort (Kahn's Algorithm)
Try It Yourself
Summary & Next Steps

1. Number of Islands

Problem: Given a 2D grid of '1' (land) and '0' (water), count the number of islands — groups of adjacent land cells connected horizontally or vertically.

The grid is an implicit graph: each cell is a node, and its up/down/left/right neighbors are its edges. This is Chapter 3's connected-components problem wearing a grid costume.

def num_islands(grid):
    if not grid:
        return 0
 
    rows, cols = len(grid), len(grid[0])
    visited = set()
 
    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == "0" or (r, c) in visited):
            return
        visited.add((r, c))
        dfs(r + 1, c)     # down
        dfs(r - 1, c)     # up
        dfs(r, c + 1)     # right
        dfs(r, c - 1)     # left
 
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visited:
                dfs(r, c)             # "flood fill" — mark the whole island visited
                islands += 1
 
    return islands
 
grid = [
    ["1", "1", "0", "0"],
    ["1", "1", "0", "0"],
    ["0", "0", "1", "0"],
    ["0", "0", "0", "1"],
]
print(num_islands(grid))     # 3

Complexity: O(rows × cols) — each cell is visited at most once thanks to the visited set, and the DFS "flood fill" from each unvisited land cell explores exactly that island before moving on.

2. Detect a Cycle in a Directed Graph

Chapter 3's undirected cycle detection doesn't directly transfer to directed graphs — going back to your parent isn't automatically safe, because directed edges only go one way. Instead, track two sets: nodes fully finished processing, and nodes currently in progress (on the current DFS path). A cycle exists if DFS reaches a node that's still in progress.

def has_cycle_directed(graph, all_nodes):
    WHITE, GRAY, BLACK = 0, 1, 2      # unvisited, in-progress, finished
    state = {node: WHITE for node in all_nodes}
 
    def dfs(node):
        state[node] = GRAY                    # mark as "on the current path"
        for neighbor in graph.get(node, []):
            if state[neighbor] == GRAY:         # reached a node still on our path → cycle
                return True
            if state[neighbor] == WHITE and dfs(neighbor):
                return True
        state[node] = BLACK                     # done exploring from this node
        return False
 
    return any(state[node] == WHITE and dfs(node) for node in all_nodes)

Intuition: GRAY means "currently being explored, somewhere above me on the call stack." Reaching a GRAY node means you've looped back onto your own path — exactly a cycle. Reaching a BLACK node is fine — it means that subtree was already fully explored and found cycle-free from a different starting point.

3. Topological Sort (Kahn's Algorithm)

Problem: Given a directed acyclic graph (DAG) — e.g., course prerequisites — produce an ordering of nodes such that every edge A → B places A before B.

Kahn's algorithm repeatedly removes nodes with no remaining incoming edges (in-degree 0), since those are always safe to place next:

from collections import deque
 
def topological_sort(graph, all_nodes):
    in_degree = {node: 0 for node in all_nodes}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1          # count incoming edges for every node
 
    queue = deque([node for node in all_nodes if in_degree[node] == 0])
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1            # "remove" this edge
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    if len(order) != len(all_nodes):
        raise ValueError("Graph has a cycle — no valid topological order exists")
 
    return order
 
courses = {
    "Intro": ["DataStructures"],
    "DataStructures": ["Algorithms"],
    "Algorithms": ["Graphs"],
    "Graphs": [],
}
print(topological_sort(courses, list(courses.keys())))
# ['Intro', 'DataStructures', 'Algorithms', 'Graphs']

Complexity: O(V + E) — building in-degrees scans every edge once, and the BFS-style queue processing (Chapter 2's pattern, reused here) visits every node and edge once. If the resulting order doesn't include every node, the graph contains a cycle — a DAG-only algorithm has no valid ordering otherwise.

4. Try It Yourself

# (a) Max Area of Island — like Number of Islands, but return the size of the LARGEST island
def max_area_of_island(grid):
    ...
 
# (b) Clone Graph — given a reference node in a connected graph, return a deep copy of the graph
def clone_graph(node):
    ...

Answers (click to expand)

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()
 
    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == 0 or (r, c) in visited):
            return 0
        visited.add((r, c))
        return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
 
    return max(
        (dfs(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 1),
        default=0,
    )
    # Same flood-fill template as Number of Islands, accumulating a count instead of just marking visited
 
# (b) sketch: BFS/DFS from `node`, using a dict {original_node: cloned_node} in place of
# a plain visited set — Module 8's hash map doubles as both "have I seen this" AND
# "what's its corresponding clone," reusing the exact BFS/DFS traversal templates above.

5. Summary & Next Steps

Key Takeaways

A 2D grid is an implicit graph — each cell is a node, adjacent cells are edges — so grid problems (Number of Islands) reduce directly to connected-components DFS/BFS.
Directed-graph cycle detection needs a three-state tracker (unvisited / in-progress / finished), since revisiting a finished node is fine but revisiting an in-progress node signals a cycle.
Topological sort (Kahn's algorithm) repeatedly peels off zero-in-degree nodes using a queue — it's BFS's queue-processing pattern applied to dependency ordering, and only succeeds if the graph has no cycles.

Concept Check

Why is a 2D grid problem like Number of Islands really a connected-components problem in disguise?
Why does directed-graph cycle detection need three states instead of undirected detection's simple "visited or not"?
What does it mean if Kahn's algorithm produces an order shorter than the total number of nodes?

Next Module

→ Module 10: Dynamic Programming & Greedy

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index