Essential Graph Algorithms for Coding Interviews

1. How to Spot a Graph Problem in Disguise

During an interview at a major tech company, you rarely receive a prompt that explicitly says, "Here is a directed acyclic graph, please traverse it." Instead, graph problems are usually disguised as real-world scenarios or grid-based puzzles.

You should immediately start thinking about graph algorithms if the problem description involves any of the following themes:

• Connections: "Find people who are friends of friends," "Determine if there is a flight between City A and City B."
• Dependencies: "You have a list of tasks and prerequisites, what order should you complete them?" or "Compile a project with dependencies."
• Grids and Mazes: "Find the shortest path out of this 2D array maze," "Count the number of islands in a grid."
• Transformations: "Change one word into another word by changing a single letter at a time (Word Ladder)."

Once you identify the problem as a graph problem, your next step is to figure out the best representation. Adjacency Lists (using Hash Maps or Lists of Lists) are generally the best choice for interview settings because they are memory efficient and fast to iterate over. Grids (2D arrays) act as implicit graphs, where each cell is a node and its adjacent cells are its edges.

2. Pattern 1: Breadth-First Search (BFS) for Shortest Paths

Breadth-First Search is your go-to algorithm whenever a problem asks for the "shortest path" or the "minimum number of steps" in an unweighted graph.

BFS explores the graph level by level, radiating outward like ripples in a pond. Because it explores all nodes at a distance of 1 before exploring any nodes at a distance of 2, the first time it reaches the destination node, it is guaranteed to have found the shortest path.

Key Identifying Keywords:

Shortest path, minimum steps, closest, nearest, level-order traversal.

Implementation Pattern (Python):

BFS always requires a Queue (FIFO data structure) and a Visited Set to prevent infinite loops.

from collections import deque

def bfs_shortest_path(graph, start, target):
    queue = deque([(start, 0)]) # (current_node, distance)
    visited = set([start])
    
    while queue:
        node, distance = queue.popleft()
        
        if node == target:
            return distance
            
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
                
    return -1 # Path not found

Classic LeetCode Problems: Word Ladder, Shortest Path in Binary Matrix, Rotting Oranges.

3. Pattern 2: Depth-First Search (DFS) for Connectivity

Depth-First Search explores a graph by going as deep as possible down one path before backtracking. While it is rarely used to find the shortest path, it is incredibly efficient for exploring the entire structure of a graph, finding components, or checking if a path exists at all.

DFS is highly favored in interviews because it can be implemented very concisely using recursion.

Key Identifying Keywords:

Connectivity, reachability, all paths, exploring regions, backtracking, deep search.

Implementation Pattern (Python):

DFS requires a Stack (LIFO), which is most commonly handled implicitly by the call stack via recursion.

def dfs_traverse(graph, start, visited=None):
    if visited is None:
        visited = set()
        
    visited.add(start)
    # Process the node here
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_traverse(graph, neighbor, visited)
            
    return visited

Note: If you are doing backtracking (like finding all valid paths or permutations), you will need to remove the node from the `visited` set after the recursive call returns.

Classic LeetCode Problems: Number of Islands, Clone Graph, Pacific Atlantic Water Flow.

4. Pattern 3: Topological Sorting for Dependencies

If a problem asks you to order items based on prerequisites, you need Topological Sorting. This algorithm only works on Directed Acyclic Graphs (DAGs). If there is a cycle (e.g., Task A requires Task B, and Task B requires Task A), a topological sort is impossible.

The most intuitive way to implement this in an interview is using Kahn's Algorithm, which relies on calculating the "in-degree" (number of incoming edges) of every node.

Key Identifying Keywords:

Prerequisites, dependencies, scheduling, ordering, compiling, resolving.

Implementation Pattern (Python):

from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    # 1. Build Graph and In-Degree array
    graph = defaultdict(list)
    in_degree = {i: 0 for i in range(num_courses)}
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
        
    # 2. Find all nodes with 0 in-degree (no prerequisites)
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    top_order = []
    
    # 3. Process the queue
    while queue:
        node = queue.popleft()
        top_order.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    # 4. Check for cycles
    if len(top_order) == num_courses:
        return top_order
    return [] # Cycle detected

Classic LeetCode Problems: Course Schedule I & II, Alien Dictionary.

5. Pattern 4: Union-Find (Disjoint Sets) for Connected Components

Union-Find is a specialized data structure used specifically to track the partitioning of a set into disjoint sub-sets. It answers two questions blazingly fast (in nearly O(1) time):

1. Are Node A and Node B in the same component?
2. Can we merge the component containing Node A with the component containing Node B?

It is the perfect tool for finding cycles in undirected graphs or grouping items dynamically.

Key Identifying Keywords:

Connected components, dynamic connectivity, grouping, redundant connection, merging sets.

Implementation Pattern (Python):

You must memorize the implementation of a Union-Find class, specifically remembering to include Path Compression in the `find` method to ensure optimal time complexity.

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False # Already in same set (cycle detected)
            
        # Union by rank
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            
        return True

Classic LeetCode Problems: Redundant Connection, Number of Connected Components in an Undirected Graph, Accounts Merge.

6. Pattern 5: Dijkstra's for Weighted Shortest Path

If the problem asks for the shortest path, but the edges have weights (costs, times, distances), standard BFS will fail. You need Dijkstra's algorithm.

Dijkstra's is essentially BFS, but instead of a standard Queue, it uses a Priority Queue (Min-Heap) to ensure that you always explore the cheapest available path next.

Key Identifying Keywords:

Shortest path with costs, cheapest flight, minimum time, network delay.

Implementation Pattern (Python):

import heapq

def dijkstra(graph, start, target):
    # Priority queue stores tuples of (total_cost, node)
    pq = [(0, start)]
    # Dictionary to keep track of the minimum cost to reach each node
    min_cost = {start: 0}
    
    while pq:
        current_cost, node = heapq.heappop(pq)
        
        # If we reached the target, this is guaranteed to be the shortest path
        if node == target:
            return current_cost
            
        # If we found a shorter path previously, ignore this older tuple
        if current_cost > min_cost.get(node, float('inf')):
            continue
            
        for neighbor, weight in graph[node]:
            new_cost = current_cost + weight
            
            # Only push to queue if we found a strictly better path
            if new_cost < min_cost.get(neighbor, float('inf')):
                min_cost[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor))
                
    return -1

Classic LeetCode Problems: Network Delay Time, Cheapest Flights Within K Stops (Note: Bellman-Ford is also good for this one), Path With Maximum Probability.