DSA: Graph Traversal Patterns

Solution to Last Week's Challenge

Last week's problem was: DSA: Binary Search Patterns

The optimal solution uses dsa: binary search patterns pattern with careful state management.

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)

Introduction

Graph traversal is arguably the most critical pattern to master for technical interviews at top-tier engineering firms. Unlike linear data structures such as arrays or linked lists, graphs represent complex, non-linear relationships that mirror real-world systems. From the social mapping of LinkedIn connections to the routing protocols that power the internet, graph algorithms are the invisible engine of modern software architecture. For an engineer, the ability to navigate these structures efficiently is not just a coding skill; it is a fundamental requirement for building scalable, interconnected systems.

In a technical interview, graph problems often serve as a filter for high-level candidates. They test your ability to handle recursion, manage state (specifically tracking visited nodes), and choose the correct search strategy—Breadth-First Search (BFS) or Depth-First Search (DFS)—based on the constraints of the problem. Mastering these patterns allows you to transform abstract "nodes and edges" into concrete solutions for pathfinding, connectivity, and dependency resolution.

Theory

At its core, graph traversal is the process of visiting every vertex and edge in a graph in a systematic order. The two primary strategies are Depth-First Search (DFS) and Breadth-First Search (BFS). DFS dives as deep as possible into a branch before backtracking, making it ideal for exploring all possible paths. BFS, conversely, explores all neighbors at the current depth before moving to the next level, making it the gold standard for finding the shortest path in unweighted graphs.

Understanding the underlying representation of a graph—usually an Adjacency List or an Adjacency Matrix—is vital. While a matrix offers $O(1)$ edge lookups, it consumes $O(V^2)$ space. An adjacency list is almost always preferred in interviews due to its $O(V + E)$ space efficiency.

The complexity for both BFS and DFS is generally $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. The space complexity is $O(V)$ to account for the recursion stack (DFS) or the queue (BFS) and the visited set.

Pattern Visualization

Choosing between BFS and DFS is the first hurdle in any graph problem. The following logic flow helps determine the optimal approach based on the problem requirements.

Implementation

Let's look at a standard implementation using an Adjacency List in Python. We will implement both a recursive DFS and an iterative BFS.

from collections import deque

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    # Brute Force / Standard BFS
    def bfs(self, start_node):
        visited = set()
        queue = deque([start_node])
        visited.add(start_node)
        result = []

        while queue:
            node = queue.popleft()
            result.append(node)
            
            for neighbor in self.graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return result # Time: O(V+E), Space: O(V)

    # Optimized Recursive DFS
    def dfs(self, start_node):
        visited = set()
        result = []

        def traverse(node):
            visited.add(node)
            result.append(node)
            for neighbor in self.graph.get(node, []):
                if neighbor not in visited:
                    traverse(neighbor)
        
        traverse(start_node)
        return result # Time: O(V+E), Space: O(V)

Complexity Analysis Table

Common Patterns

1. Cycle Detection (Undirected Graph)

Detecting cycles is a classic interview question. In DFS, if we encounter a neighbor that is already visited and is not the parent of the current node, a cycle exists.

def has_cycle(node, parent, visited, adj):
    visited.add(node)
    for neighbor in adj[node]:
        if neighbor not in visited:
            if has_cycle(neighbor, node, visited, adj):
                return True
        elif neighbor != parent:
            return True
    return False

2. Number of Islands (Grid Traversal)

Grids are implicit graphs. Each cell (r, c) has edges to (r+1, c), (r-1, c), etc.

def numIslands(grid):
    if not grid: return 0
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                # Start a DFS to sink the island
                self.dfs_sink(grid, r, c)
                count += 1
    return count

Practice Problems

To master these patterns, you should tackle problems in increasing order of complexity. The following chart maps common LeetCode-style problems by their frequency in FAANG interviews and their relative difficulty.

This Week's Interview Challenge

Problem: The Social Distance Tracker

In a social network, people are represented as nodes, and friendships are undirected edges. Due to a new digital update, a "feature" is released to a specific person. This feature spreads to all their direct friends, then to their friends' friends, and so on.

Given an undirected graph of friendships and a starting person S, find the minimum number of "steps" required for the feature to reach a target person T. If T cannot be reached, return -1.

Example 1:

• Input: adj = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}, start = 0, target = 3
• Output: 2 (0 -> 1 -> 3)

Example 2:

• Input: adj = {0: [1], 1: [0], 2: [3], 3: [2]}, start = 0, target = 3
• Output: -1

Constraints:

• $1 \le V \le 10^4$
• $0 \le E \le 10^5$
• The graph is undirected.

Hints:

1. Is this asking for the shortest path or any path?
2. Which data structure is best for level-by-level traversal?
3. How do you ensure you don't get stuck in an infinite loop if there is a cycle (e.g., A is friends with B, B is friends with A)?
4. Track the "distance" or "level" as you traverse.

Template Code:

def min_steps_to_target(adj, start, target):
    # Your code here
    pass

# Submit your solution and check back next week for the detailed answer!

Conclusion

Graph traversal is more than just a coding exercise; it is a way of thinking about connectivity. When approaching a graph problem, always start by identifying the graph type (directed vs. undirected) and the goal (shortest path vs. exhaustive search). Remember to always use a visited set to handle cycles—this is the most common mistake made during live coding sessions. By mastering BFS and DFS, you unlock the ability to solve a vast array of problems ranging from simple connectivity to complex dependency mapping.

https://visualgo.net/en/dfsbfs https://leetcode.com/tag/graph/ https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/