Chapter 5: Graphs - Coding Interview Algorithms

1. Graph Representation

📌 When and Where to Use

Adjacency List: Sparse graphs (few edges), most common in interviews
Adjacency Matrix: Dense graphs (many edges), fast edge lookup
Real-world example: Social networks, web pages (links), road maps, dependencies in build systems, or network routing

Adjacency List (Most Common)

# Graph representation using adjacency list
# graph[i] is a list of neighbors of node i

graph = {
    0: [1, 2],      # Node 0 connects to nodes 1 and 2
    1: [0, 3],      # Node 1 connects to nodes 0 and 3
    2: [0, 3],      # Node 2 connects to nodes 0 and 3
    3: [1, 2]       # Node 3 connects to nodes 1 and 2
}

# For weighted graphs, store tuples (neighbor, weight)
weighted_graph = {
    0: [(1, 5), (2, 3)],  # Node 0: edge to 1 with weight 5, edge to 2 with weight 3
    1: [(0, 5), (3, 2)],
    2: [(0, 3), (3, 1)],
    3: [(1, 2), (2, 1)]
}

2. DFS (Depth-First Search)

📌 When and Where to Use

Path finding: Finding any path between nodes
Cycle detection: Detecting cycles in directed/undirected graphs
Connected components: Finding all connected components
Topological sort: Ordering nodes with dependencies
Real-world example: Maze solving, finding connected users in social network, detecting circular dependencies, or exploring all reachable nodes

Example: DFS Traversal

def dfs(graph, start):
    """
    Depth-First Search traversal of graph.
    
    Args:
        graph: Adjacency list representation
        start: Starting node
    
    Returns:
        List of visited nodes in DFS order
    """
    # Step 1: Initialize visited set and result
    visited = set()
    result = []
    
    def dfs_helper(node):
        # Step 2: Mark current node as visited
        visited.add(node)
        result.append(node)
        
        # Step 3: Visit all unvisited neighbors
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                # Step 3a: Recursively visit neighbor
                dfs_helper(neighbor)
    
    # Step 4: Start DFS from start node
    dfs_helper(start)
    return result

Step-by-Step Code Walkthrough:

Step 1 - Initialize: Create visited set to track visited nodes and result list.

Step 2 - Mark Visited: Add current node to visited set and result.

Step 3 - Visit Neighbors: For each neighbor:

Step 3a: If not visited, recursively call DFS on it
This explores as deep as possible before backtracking

Step 4 - Start: Begin DFS from start node.

Key Property: DFS explores one path completely before backtracking.

Time Complexity:

O(V + E) where V = vertices, E = edges

Space Complexity:

O(V) for visited set and recursion stack

3. BFS (Breadth-First Search)

📌 When and Where to Use

Shortest path (unweighted): Finding shortest path in unweighted graphs
Level-order: Processing nodes level by level
Minimum steps: Finding minimum steps to reach target
Real-world example: Finding shortest route in unweighted network, social network degrees of separation, or level-order processing

Example: BFS Traversal

from collections import deque

def bfs(graph, start):
    """
    Breadth-First Search traversal of graph.
    
    Args:
        graph: Adjacency list representation
        start: Starting node
    
    Returns:
        List of visited nodes in BFS order
    """
    # Step 1: Initialize queue and visited set
    queue = deque([start])
    visited = set([start])
    result = []
    
    # Step 2: Process nodes level by level
    while queue:
        # Step 3: Dequeue current node
        node = queue.popleft()
        result.append(node)
        
        # Step 4: Visit all unvisited neighbors
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                # Step 4a: Mark as visited
                visited.add(neighbor)
                # Step 4b: Add to queue for next level
                queue.append(neighbor)
    
    return result

Step-by-Step Code Walkthrough:

Step 1 - Initialize: Queue starts with start node, mark it as visited.

Step 2 - Loop: Continue while queue has nodes (process level by level).

Step 3 - Dequeue: Remove node from front of queue and add to result.

Step 4 - Visit Neighbors: For each unvisited neighbor:

Step 4a: Mark as visited
Step 4b: Add to queue (will be processed in next level)

Key Property: BFS processes all nodes at distance k before nodes at distance k+1.

4. Shortest Path (Unweighted Graph)

Example: Shortest Path Using BFS

from collections import deque

def shortest_path(graph, start, end):
    """
    Find shortest path between two nodes using BFS.
    
    Args:
        graph: Adjacency list representation
        start: Starting node
        end: Target node
    
    Returns:
        List representing shortest path, or [] if no path exists
    """
    # Step 1: Initialize queue and parent map
    queue = deque([start])
    visited = set([start])
    parent = {start: None}  # Track parent to reconstruct path
    
    # Step 2: BFS to find target
    while queue:
        node = queue.popleft()
        
        # Step 3: Check if we reached target
        if node == end:
            # Step 3a: Reconstruct path using parent map
            path = []
            current = end
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]  # Reverse to get start → end
        
        # Step 4: Explore neighbors
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node  # Track parent for path reconstruction
                queue.append(neighbor)
    
    # Step 5: No path found
    return []

Step-by-Step Code Walkthrough:

Step 1 - Initialize: Queue, visited set, and parent map (to reconstruct path).

Step 2 - BFS: Standard BFS traversal.

Step 3 - Target Found: If we reach target:

Step 3a: Reconstruct path by following parent pointers backwards
Reverse to get path from start to end

Step 4 - Explore: For each neighbor, mark visited, set parent, and add to queue.

Step 5 - No Path: If BFS completes without finding target, return empty list.

5. Topological Sort

📌 When and Where to Use

Dependency resolution: Ordering tasks with dependencies
Course prerequisites: Ordering courses based on prerequisites
Build systems: Determining build order
Real-world example: Compiling source files with dependencies, installing packages with dependencies, or scheduling tasks with prerequisites

Example: Topological Sort (Kahn's Algorithm)

from collections import deque

def topological_sort(graph):
    """
    Topological sort using Kahn's algorithm (BFS-based).
    
    Args:
        graph: Adjacency list (directed acyclic graph)
    
    Returns:
        List of nodes in topological order, or [] if cycle exists
    """
    # Step 1: Calculate in-degree for each node
    # In-degree = number of incoming edges
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
    
    # Step 2: Initialize queue with nodes having in-degree 0
    # These have no dependencies, can be processed first
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []
    
    # Step 3: Process nodes
    while queue:
        # Step 3a: Dequeue node with no dependencies
        node = queue.popleft()
        result.append(node)
        
        # Step 3b: Reduce in-degree of neighbors
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            # Step 3c: If neighbor has no dependencies, add to queue
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Step 4: Check for cycle
    # If result length < total nodes, cycle exists
    if len(result) != len(graph):
        return []  # Cycle detected
    
    return result

Step-by-Step Code Walkthrough:

Step 1 - Calculate In-Degree: Count incoming edges for each node (dependencies).

Step 2 - Initialize Queue: Start with nodes having in-degree 0 (no dependencies).

Step 3 - Process:

Step 3a: Dequeue node (add to result)
Step 3b: Reduce in-degree of all neighbors
Step 3c: If neighbor's in-degree becomes 0, add to queue

Step 4 - Cycle Check: If not all nodes processed, cycle exists (can't topologically sort).

6. Union-Find (Disjoint Set)

📌 When and Where to Use

Connected components: Finding connected components efficiently
Cycle detection: Detecting cycles in undirected graphs
Kruskal's algorithm: Minimum spanning tree
Real-world example: Network connectivity, image segmentation, or grouping related items

Example: Union-Find Implementation

class UnionFind:
    """Union-Find data structure with path compression and union by rank"""
    
    def __init__(self, n):
        # Step 1: Initialize parent array
        # Initially, each node is its own parent
        self.parent = list(range(n))
        # Step 2: Initialize rank array (for union by rank)
        self.rank = [0] * n
    
    def find(self, x):
        # Step 3: Find root with path compression
        if self.parent[x] != x:
            # Step 3a: Recursively find root
            # Step 3b: Path compression: make parent point directly to root
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Step 4: Union two sets
        root_x = self.find(x)
        root_y = self.find(y)
        
        # Step 5: If already in same set, return
        if root_x == root_y:
            return
        
        # Step 6: Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            # Attach smaller tree under larger tree
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            # Same rank, attach one to other and increase rank
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

Step-by-Step Code Walkthrough:

Step 1 - Initialize Parent: Each node starts as its own parent (separate sets).

Step 2 - Initialize Rank: Track tree height for union by rank optimization.

Step 3 - Find: Find root with path compression:

Step 3a: Recursively find root
Step 3b: Make parent point directly to root (compression)

Step 4 - Union: Find roots of both sets.

Step 5 - Same Set: If same root, already connected.

Step 6 - Union by Rank: Attach smaller tree under larger tree to keep tree balanced.

Time Complexity:

Nearly O(1) per operation with path compression and union by rank

📚 Chapter Summary

DFS: Use for path finding, cycle detection, connected components
BFS: Use for shortest path (unweighted), level-order processing
Topological Sort: Use for dependency ordering, prerequisite problems
Union-Find: Use for connected components, cycle detection, MST

Key Takeaway: Graph problems often require choosing between DFS (deep exploration) and BFS (level-by-level). Use topological sort for dependency problems and Union-Find for connectivity.