Master Graph Traversal Patterns (DFS & BFS)

You've spent hours wrestling with LeetCode’s “Number of Islands.” You finally crack it—only to freeze when the interviewer throws you a graph with teleporters, or asks for the shortest transformation sequence between words. Your mind races: DFS? BFS? Union-Find? Suddenly, all those “graph problems” blur together.

Sound familiar?

Here’s the catch: most candidates memorize individual solutions, not the patterns. But beneath the surface, nearly every FAANG graph question—whether it’s about islands, word ladders, or social networks—boils down to one of 11 Graph Traversal Patterns. Mastering these is the difference between flailing and flowing in your interview.

What You'll Learn

By the end of this guide, you’ll confidently master:

✅ The 11 sub-patterns behind real FAANG graph questions
✅ Pattern recognition skills to decode any DFS/BFS-based problem
✅ 60 curated practice problems from Google, Amazon, Facebook, Microsoft, and more
✅ When to use each pattern with sharp recognition triggers
✅ Common pitfalls (and how to dodge them like a pro)
✅ A 3-week roadmap to go from graph-wary to graph-wizard

What is Graph Traversal Patterns (DFS & BFS)?

Imagine exploring a mysterious maze. You can wander down one path until you hit a wall (DFS: “Deep Sea Fishing”) or systematically check each room level by level (BFS: “Breadth-First Searchlight”). Graph Traversal Patterns are your toolkit for navigating these mazes—whether you’re mapping islands, building dependency trees, or finding the fastest route in a city.

The core insight?
Graphs are everywhere—social networks, maps, dependency graphs—but the problems you see in interviews are built from a handful of reusable traversal and connectivity “templates”. Each template leverages either depth-first search (DFS) or breadth-first search (BFS), sometimes in creative hybrids.

Why This Pattern Matters

Coverage: Over 25% of FAANG interview rounds feature graph traversal problems (DFS/BFS or a subpattern).
Optimization: Naive brute force is rarely feasible—these patterns unlock O(N+E) solutions where N = nodes, E = edges.
Transferable: Mastering traversal unlocks other patterns: cycle detection, shortest path, MST, etc.
Versatility: Real-world systems—from Facebook’s friend recommendation to Amazon’s delivery routes—are powered by these patterns.

Companies that frequently ask graph traversal questions: Google, Amazon, Facebook (Meta), Microsoft, Apple, Uber, Bloomberg, ByteDance, Oracle, Pinterest, Airbnb

The 11 Graph Traversal Patterns (DFS & BFS) Sub-Patterns

Let’s break down each sub-pattern with detailed examples, key insights, and must-practice problems.

1. Bidirectional BFS (BFS Optimization for Known Source & Target)

What it is:
Bidirectional BFS is an advanced search technique where you run two BFS traversals simultaneously—one from the source node, one from the target—meeting in the middle. It’s the fastest way to find the shortest path when both endpoints are known.

Key insight:
Traditional BFS explores from one end, potentially traversing the entire graph. Bidirectional BFS cuts the search space exponentially by growing two frontiers until they intersect. Think of two teams digging a tunnel toward each other: they meet in the middle, halving the work.

How it works:

Initialize two queues: one for the source, one for the target.
Alternate expanding one level from each queue.
Track visited nodes for both sides.
When a node is found in both visited sets, the shortest path is found.

When to use:

When both the start and target nodes are given.
The graph is undirected or allows bidirectional movement.
Finding the shortest transformation sequence (word ladder, bus routes, etc.).
The search space is too large for one-sided BFS.

Recognition triggers:

“Find the shortest path between X and Y”
Start and end are both specified
Constraints make single-source BFS too slow

Essential Problems:

Hard:

Word Ladder II - Uber, Amazon, Facebook, Box, Lyft ⭐
Find all shortest transformation sequences—a classic bidirectional BFS fit.
Bus Routes - Amazon, Square, Uber

💡 Pro Tip:
In interviews, always clarify if both the start and end are known. Bidirectional BFS can reduce time complexity from O(N) to O(√N) in many cases.

⚠️ Common Mistake:
Not maintaining separate visited sets for each direction. This can cause loops or miss the meeting point. Always track visited nodes for both searches!

Example Code Pattern:

PYTHON
from collections import deque

def bidirectional_bfs(start, end, graph):
    if start == end:
        return 0

    visited_start = {start}
    visited_end = {end}
    queue_start = deque([start])
    queue_end = deque([end])
    level = 0

    while queue_start and queue_end:
        level += 1
        # Always expand the smaller frontier
        if len(queue_start) > len(queue_end):
            queue_start, queue_end = queue_end, queue_start
            visited_start, visited_end = visited_end, visited_start

        for _ in range(len(queue_start)):
            node = queue_start.popleft()
            for neighbor in graph[node]:
                if neighbor in visited_end:
                    return level  # meeting point!
                if neighbor not in visited_start:
                    visited_start.add(neighbor)
                    queue_start.append(neighbor)
    return -1  # not connected

Time/Space Complexity:
O(N+E), but usually much faster in practice: O(√N) levels.

2. Bridges & Articulation Points (Tarjan Low-Link)

What it is:
This pattern identifies critical edges (bridges) and critical nodes (articulation points) whose removal increases the number of connected components in a graph. Tarjan’s algorithm (using DFS and low-link values) is the standard approach.

Key insight:
By tracking the earliest reachable ancestor (low-link value) during DFS, you can detect if a node or edge is a “single point of failure” in the network—removing it breaks connectivity.

How it works:

Run DFS, assigning each node a discovery time.
Track the lowest discovery time reachable from each node’s subtree (low-link).
If a child can’t reach an ancestor of the parent, the edge is a bridge.
If a node’s removal splits the graph, it’s an articulation point.

When to use:

Network reliability analysis (find weak links)
“Find all critical connections/bridges in a network”
“What nodes/edges disconnect the graph?”
Social network or communication design questions

Recognition triggers:

“Remove as few nodes/edges as possible to disconnect the network”
“Find all critical/weak links”
Questions using words like “bridge”, “articulation”, “cut node”

Essential Problems:

Hard:

Critical Connections in a Network - Amazon, Adobe ⭐
Classic Tarjan’s bridge-finding problem.
Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree - Amazon

💡 Pro Tip:
Low-link values are the minimum of a node’s own discovery time and all its descendants’ low-links. Always backtrack correctly during DFS to update these.

⚠️ Common Mistake:
Forgetting to differentiate between parent and child nodes during DFS, leading to false positives for bridges/articulation points. Always skip the parent edge!

Example Code Pattern:

PYTHON
def tarjan_bridges(n, graph):
    res = []
    ids = [None] * n
    low = [None] * n
    time = [0]

    def dfs(u, parent):
        ids[u] = low[u] = time[0]
        time[0] += 1
        for v in graph[u]:
            if ids[v] is None:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > ids[u]:
                    res.append((u, v))  # Bridge found
            elif v != parent:
                low[u] = min(low[u], ids[v])

    for i in range(n):
        if ids[i] is None:
            dfs(i, -1)
    return res

Time/Space Complexity:
O(N+E), where N = nodes, E = edges.

3. Deep Copy / Cloning

What it is:
Deep copy (cloning) patterns create an exact duplicate of a graph or complex linked structure, preserving all node values and pointers—including cycles and “random” pointers.

Key insight:
To avoid infinite loops (from cycles), use a hash map that tracks already-cloned nodes. For each node, clone it if it hasn’t been seen, then recursively/iteratively clone its neighbors.

How it works:

Use DFS or BFS to traverse the graph.
For each node, check if it’s already cloned in a hash map.
If not, create a new node and add it to the map.
Recursively/iteratively clone all neighbors.

When to use:

“Copy” or “clone” a graph, linked list, or tree
Structures with random pointers or cycles
Building a parallel data structure

Recognition triggers:

“Return a deep copy”
“Each node has a list of neighbors/random pointers”
Cycles or multiple references possible

Essential Problems:

Medium:

Clone Graph - Facebook, Amazon, Microsoft, Bloomberg, Apple ⭐
Classic cloning with cycles and neighbor lists.
Copy List with Random Pointer - Amazon, Facebook, Microsoft, Bloomberg, eBay ⭐
Linked list with ‘random’ pointers—tricky edge cases.
Clone N-ary Tree - Amazon
Find the City With the Smallest Number of Neighbors at a Threshold Distance - Citrix

💡 Pro Tip:
In DFS, always handle the “visited” check before recursion to avoid infinite loops on cyclic graphs.

⚠️ Common Mistake:
Creating new nodes without storing them in a visited map. This leads to duplicate nodes and incorrect neighbor links—especially dangerous with cycles!

Example Code Pattern:

PYTHON
def cloneGraph(node):
    if not node:
        return None
    cloned = {}

    def dfs(n):
        if n in cloned:
            return cloned[n]
        copy = Node(n.val)
        cloned[n] = copy
        for neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy

    return dfs(node)

Time/Space Complexity:
O(N), where N = number of nodes.

4. Graph BFS – Connected Components / Island Counting

What it is:
Use BFS to traverse all nodes in a component, often to count the number of islands (connected regions) or to process all nodes at a given “distance/level”.

Key insight:
BFS ensures you visit all reachable nodes from a starting point before moving to other components—making it ideal for “level-order” and “minimum steps” problems.

How it works:

Iterate over all nodes/cells.
For each unvisited node, start BFS and mark all reachable nodes.
Increment connected component counter as needed.

When to use:

“Number of islands”, “count connected components”
“Find shortest path in a grid/matrix”
“Minimum steps to spread/convert X in a grid”

Recognition triggers:

2D grid or matrix, “island”, “region”, “component”
“Shortest path in grid/matrix” with 4/8 directions
“Spread” or “rot” across levels

Essential Problems:

Medium:

01 Matrix - Amazon, Microsoft ⭐
BFS from all zeroes to fill shortest distances.
Rotting Oranges - Amazon, Google, Microsoft, Bloomberg, Oracle
Level-order BFS to simulate rot spread.
Shortest Path in Binary Matrix - Amazon, Google, Facebook, Oracle, Snapchat

Hard:

Word Ladder - Amazon, Facebook, Lyft, Microsoft, Google ⭐
Transform one word to another in minimum steps; classic BFS.

💡 Pro Tip:
When working with a grid, use a queue and pre-mark visited cells before enqueuing. This prevents re-processing and saves time.

⚠️ Common Mistake:
Forgetting to mark cells as visited before enqueuing them. This can cause duplicate visits and TLE (time limit exceeded).

Example Code Pattern:

PYTHON
from collections import deque

def numIslands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0

    for r in range(rows):
        for c in range(cols):
            if (r, c) not in visited and grid[r][c] == '1':
                queue = deque([(r, c)])
                visited.add((r, c))
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                        nx, ny = x+dx, y+dy
                        if 0<=nx<rows and 0<=ny<cols and (nx, ny) not in visited and grid[nx][ny] == '1':
                            queue.append((nx, ny))
                            visited.add((nx, ny))
                count += 1
    return count

Time/Space Complexity:
O(N×M), N=rows, M=cols.

5. Graph BFS – Topological Sort (Kahn’s Algorithm)

What it is:
BFS-based topological sort (Kahn’s Algorithm) orders nodes in a Directed Acyclic Graph (DAG) so that for every edge u → v, u comes before v. Often used for dependency resolution.

Key insight:
Nodes with zero incoming edges (in-degree zero) can be safely processed first. Remove them and update the in-degree of neighbors; repeat until all nodes are processed.

How it works:

Calculate in-degree for each node.
Place nodes with in-degree zero in a queue.
Remove nodes from queue, decrement in-degree of their neighbors.
Add newly zero in-degree nodes to queue.
If all nodes are processed, you have a valid topological order.

When to use:

“Ordering tasks/recipes/courses with dependencies”
“Can you finish all tasks?”
“Build order” problems

Recognition triggers:

“Prerequisites”, “dependencies”, “courses”, “build order”
DAG or explicit directionality
“Order so that…”

Essential Problems:

Medium:

Sequence Reconstruction - Google
Parallel Courses - Google, Uber
Minimum Height Trees - Facebook ⭐
Find root nodes that minimize tree height; requires in-degree analysis.
Find All Possible Recipes from Given Supplies

Hard:

Parallel Courses III
Largest Color Value in a Directed Graph
Build a Matrix With Conditions
Alien Dictionary - Facebook, Amazon, Airbnb, Pinterest, Google ⭐
Infers letter order from dictionary—classic topological sort.

💡 Pro Tip:
If you need any valid order, Kahn’s is great. If you need all possible orders or to detect cycles, track visited node count vs total nodes.

⚠️ Common Mistake:
Not handling cycles—if not all nodes are processed, the graph has cycles (no valid ordering). Always check for this!

Example Code Pattern:

PYTHON
from collections import deque, defaultdict

def kahn_topological_sort(numNodes, edges):
    graph = defaultdict(list)
    indegree = [0] * numNodes
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(numNodes) if indegree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    if len(order) == numNodes:
        return order
    else:
        return []  # Cycle detected; no valid ordering

Time/Space Complexity:
O(N+E), N=nodes, E=edges.

6. Graph DFS – Connected Components / Island Counting

What it is:
DFS can also be used to traverse all nodes in a connected component—especially effective for recursive solutions to grid/graph problems.

Key insight:
DFS dives as deep as possible along each branch before backtracking. This is handy for marking all reachable nodes, especially in recursive “flood fill” and “island” counting.

How it works:

For each unvisited node/cell, call DFS.
Mark the node as visited.
Recursively visit all neighbors.
Count or aggregate results as needed.

When to use:

“Number of islands”, “flood fill”, “find all connected regions”
Problems with recursive/stack-based exploration
When you need to process all nodes in a component before moving on

Recognition triggers:

2D grid, “island”, “region”, “enclave”
“Flip surrounded regions”, “flood fill”
Recursive structure fits the problem

Essential Problems:

Easy:

Flood Fill - Amazon, Microsoft, Google
Change colors in a region recursively—classic DFS.

Medium:

Surrounded Regions - Google, Amazon, Uber ⭐
Flip surrounded ‘O’s to ‘X’s via DFS from borders.
Pacific Atlantic Water Flow - ByteDance, Google, Amazon
Number of Provinces - Amazon, Two Sigma, Goldman Sachs, Dropbox, Facebook
Number of Islands - Amazon, Bloomberg, Microsoft, Oracle, Facebook ⭐
DFS template for grid traversal and island counting.
Number of Enclaves - Google
Number of Closed Islands - Google, Amazon, Oracle, Uber
Count Sub Islands
Max Area of Island - Google, DoorDash, Amazon, Facebook, Microsoft
Keys and Rooms - Amazon, Twitch
Detonate the Maximum Bombs

💡 Pro Tip:
When using recursion, Python’s stack limit can be hit on large grids. Switch to iterative DFS or increase the recursion limit for big cases.

⚠️ Common Mistake:
Not marking nodes as visited before recursion—this causes infinite loops or stack overflows in cyclic graphs.

Example Code Pattern:

PYTHON
def dfs_island(grid, r, c, visited):
    rows, cols = len(grid), len(grid[0])
    if (r, c) in visited or grid[r][c] == '0':
        return
    visited.add((r, c))
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nr, nc = r+dr, c+dc
        if 0 <= nr < rows and 0 <= nc < cols:
            dfs_island(grid, nr, nc, visited)

Time/Space Complexity:
O(N×M), N=rows, M=cols.

7. Graph DFS – Cycle Detection (Directed Graph)

What it is:
DFS-based cycle detection finds whether a directed graph has a cycle—a must for checking prerequisites, course schedules, or deadlocks.

Key insight:
Use a recursion stack or node “coloring” (unvisited, visiting, visited) to detect back edges. A node revisited while “visiting” means a cycle exists.

How it works:

For each node, if unvisited, start DFS.
Mark node as “visiting”.
For each neighbor, if “visiting”, a cycle is found.
Mark node as “visited” when done.

When to use:

“Can you finish all courses/tasks?”
“Does the dependency graph have cycles?”
Checking for deadlocks or invalid orderings

Recognition triggers:

Prerequisite or dependency systems
“Cycle”, “deadlock”, “circular dependency”

Essential Problems:

Medium:

Find Eventual Safe States - Amazon
Course Schedule II - Amazon, DoorDash, Microsoft, Google, Snapchat ⭐
Topological sort with cycle-detection.
Course Schedule - Amazon, Intuit, Facebook, Karat, Microsoft
Classic cycle detection for prerequisites.
All Paths from Source Lead to Destination - Bloomberg

💡 Pro Tip:
Use three states: 0 (unvisited), 1 (visiting), 2 (visited). This coloring pattern simplifies cycle detection and is easy to implement.

⚠️ Common Mistake:
Forgetting to mark nodes as “visited” after recursion, causing false positives for cycles. Always update the state at the right time!

Example Code Pattern:

PYTHON
def has_cycle(graph, n):
    state = [0] * n  # 0=unvisited, 1=visiting, 2=visited

    def dfs(u):
        if state[u] == 1:
            return True  # cycle found
        if state[u] == 2:
            return False
        state[u] = 1
        for v in graph[u]:
            if dfs(v):
                return True
        state[u] = 2
        return False

    for i in range(n):
        if dfs(i):
            return True
    return False

Time/Space Complexity:
O(N+E), N=nodes, E=edges.

8. Minimum Spanning Tree (Kruskal / Prim / DSU + Heap)

What it is:
A Minimum Spanning Tree (MST) connects all nodes in a weighted undirected graph with the minimum total edge weight and no cycles. Kruskal’s and Prim’s are the main MST algorithms.

Key insight:
Both algorithms greedily add the next smallest edge that doesn’t form a cycle—Kruskal’s uses edge sorting and Union-Find (DSU); Prim’s uses a min-heap to grow the tree from a node.

How it works:

Kruskal: Sort all edges, use DSU to add edges without creating cycles.
Prim: Start at any node, always add the smallest edge to the tree (min-heap).

When to use:

“Connect all cities/points with minimum cost”
“Lay cables/pipes/roads with minimal resources”
Weighted undirected graphs, no negative cycles

Recognition triggers:

“Minimum cost to connect all X”
“Spanning tree”, “all nodes with least cost”
Undirected, weighted graphs

Essential Problems:

Medium:

Connecting Cities With Minimum Cost - Amazon, Uber ⭐
Direct MST application with Kruskal/Prim.
Min Cost to Connect All Points - Directi

Hard:

Optimize Water Distribution in a Village - Google, Facebook, Yahoo ⭐
MST variant with “virtual” wells and pipes.

💡 Pro Tip:
For dense graphs, prefer Prim’s with a heap. For sparse graphs, Kruskal’s with DSU is often faster.

⚠️ Common Mistake:
Not using path compression in DSU, leading to TLE on large graphs. Always optimize your Union-Find!

Example Code Pattern:

PYTHON
def kruskal_mst(n, edges):
    parent = list(range(n))

    def find(u):
        while u != parent[u]:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    def union(u, v):
        pu, pv = find(u), find(v)
        if pu == pv:
            return False
        parent[pu] = pv
        return True

    mst_weight = 0
    edges.sort(key=lambda x: x[2])
    for u, v, w in edges:
        if union(u, v):
            mst_weight += w
    return mst_weight

Time/Space Complexity:
Kruskal: O(E log E), Prim: O(E log N)

9. Shortest Path (Bellman-Ford / BFS+K)

What it is:
Find the shortest path in a graph, especially when edges have weights (possibly negative) or limited steps (e.g., K stops). Bellman-Ford and BFS with step limits are go-to patterns.

Key insight:
Bellman-Ford relaxes all edges up to K times (for K stops), handling negative weights. BFS+K limits the number of steps/edges traversed.

How it works:

Bellman-Ford: For each node, relax all outgoing edges for up to K iterations.
BFS+K: Track (node, steps) in the queue; stop when steps > K.

When to use:

“Find cheapest/shortest path with up to K stops”
Negative edge weights without negative cycles
“Minimum cost with limited transitions”

Recognition triggers:

“K stops”, “at most K edges”
Negative/variable edge costs

Essential Problems:

Medium:

Cheapest Flights Within K Stops - Facebook, Expedia, Apple, Airbnb, Amazon ⭐
BFS+K or Bellman-Ford for flight networks.
Shortest Path with Alternating Colors - Amazon

💡 Pro Tip:
If the graph is sparse and K is small, BFS+K is fast. For negative weights, Bellman-Ford is safer.

⚠️ Common Mistake:
Using Dijkstra’s algorithm when negative weights exist—it can’t handle those correctly. Default to Bellman-Ford!

Example Code Pattern:

PYTHON
from collections import deque

def bfs_k_stops(graph, src, dst, K):
    queue = deque([(src, 0, 0)])  # (node, cost, stops)
    min_cost = {}
    while queue:
        node, cost, stops = queue.popleft()
        if stops > K + 1:
            continue
        if node == dst:
            continue
        for nei, price in graph[node]:
            if stops+1 <= K+1 and (nei not in min_cost or cost+price < min_cost[nei]):
                min_cost[nei] = cost+price
                queue.append((nei, cost+price, stops+1))
    return min_cost.get(dst, -1)

Time/Space Complexity:
O(N×K), N=nodes, K=steps.

10. Shortest Path (Dijkstra’s Algorithm)

What it is:
Dijkstra’s Algorithm finds the shortest path from a source to all other nodes in a graph with non-negative edge weights using a min-heap (priority queue).

Key insight:
Always expand the node with the lowest known cost. As soon as you pop the target node from the heap, you’ve found the optimal path.

How it works:

Initialize min-heap with (cost, node).
While heap is not empty, pop the node with lowest cost.
For each neighbor, if new cost is lower, update and push to heap.
Stop when the target is reached (or all nodes processed).

When to use:

“Find the shortest/safest/easiest path”
All edge weights are non-negative
Real-world routing: maps, networks

Recognition triggers:

“Shortest/safest path”, “minimum effort/cost”
Non-negative edge weights

Essential Problems:

Medium:

Find the Safest Path in a Grid
Path With Minimum Effort - Google, Houzz, ByteDance ⭐
Dijkstra on grid with edge weights = effort.
Path with Maximum Probability - Google
Number of Ways to Arrive at Destination
Network Delay Time - Amazon ⭐
Shortest time to reach all nodes in a network.

Hard:

💡 Pro Tip:
For grid problems, treat each cell as a node and use (cost, x, y) in your heap. Pop the goal cell as soon as it’s reached—it’s guaranteed minimal.

⚠️ Common Mistake:
Not marking nodes as visited (or not updating costs properly), which can cause infinite loops or incorrect answers. Always use a cost map or visited set.

Example Code Pattern:

PYTHON
import heapq

def dijkstra(graph, start, end, n):
    heap = [(0, start)]
    dist = [float('inf')] * n
    dist[start] = 0
    while heap:
        cost, node = heapq.heappop(heap)
        if node == end:
            return cost
        for nei, w in graph[node]:
            if dist[nei] > cost + w:
                dist[nei] = cost + w
                heapq.heappush(heap, (dist[nei], nei))
    return -1

Time/Space Complexity:
O((N+E) log N), N=nodes, E=edges.

11. Union-Find (Disjoint Set Union - DSU)

What it is:
Union-Find (DSU) is a structure for efficiently tracking disjoint sets—useful for dynamic connectivity, cycle detection, and grouping problems.

Key insight:
With path compression and union by rank/size, you can merge sets and check connectivity in nearly constant time.

How it works:

Each node starts as its own parent.
Find: Recursively find the root parent (with compression).
Union: Merge two sets by updating parent pointers.
Use for connectivity checks, grouping, counting components.

When to use:

“Are X and Y in the same group/component?”
“Merge accounts/networks”
Dynamic connectivity, grouping, cycle detection

Recognition triggers:

“Merge”, “group”, “connected components”
“Redundant connection”, “valid tree”

Essential Problems:

Medium:

Regions Cut By Slashes - Uber
Redundant Connection - Amazon
Sentence Similarity II - Amazon
Most Stones Removed with Same Row or Column - Google
Graph Valid Tree - Amazon, Qualtrics, Microsoft ⭐
Check if a graph is a valid tree—cycle detection with DSU.
Accounts Merge - Facebook, Google, Amazon, Microsoft, Twitter ⭐
Group emails/accounts into merged profiles.
Number of Connected Components in an Undirected Graph - Amazon, Facebook, LinkedIn, Microsoft, Apple
The Earliest Moment When Everyone Become Friends - Google

Hard:

Number of Islands II - Amazon
Largest Component Size by Common Factor - Google

💡 Pro Tip:
Always implement path compression in your find()—it improves performance drastically, especially in large datasets.

⚠️ Common Mistake:
Not initializing each node’s parent correctly, or missing path compression—this leads to O(N) performance instead of nearly O(1).

Example Code Pattern:

PYTHON
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu != pv:
            self.parent[pu] = pv

# Time: Nearly O(1) per operation with path compression, Space: O(N)

How to Master Graph Traversal Patterns on Thita.ai

Graph problems can feel overwhelming, but Thita.ai makes mastery achievable with targeted practice and AI-powered guidance:

Pattern-Based Problem Sets Practice all 60 graph traversal problems organized by sub-pattern, so you build pattern recognition systematically.

AI Hints & Instant Feedback Stuck on whether to use BFS or DFS? Our AI coach provides context-aware hints without spoiling the solution, helping you learn the "why" behind each approach.

Real Interview Simulation Practice graph problems in timed mock interviews that mirror real FAANG conditions—complete with follow-up questions and complexity analysis.

Track Your Progress Monitor your mastery across all 11 sub-patterns on your dashboard, identifying weak spots and celebrating wins.

Your Graph Traversal Learning Roadmap

Master graph traversal in 3-4 weeks with this structured plan:

Week 1: BFS & DFS Foundations (Days 1-7)

Day 1 (1.5h): Connected Components Basics

Day 2 (1.5h): Island Problems - DFS

Day 3 (2h): Island Problems - BFS

Number of Islands (solve with BFS this time)
Surrounded Regions

Day 4 (2h): Graph Cloning

Clone Graph
Practice explaining your DFS/BFS approach out loud

Day 5 (2h): Topological Sort

Day 6-7 (3h total): Union-Find Basics

Week 2: Shortest Paths & Advanced BFS (Days 8-14)

Day 8 (2h): BFS Shortest Path

Day 9 (2.5h): Dijkstra's Algorithm

Day 10 (2h): Bellman-Ford / Special Constraints

Day 11 (2h): Bidirectional BFS

Day 12-13 (4h total): MST & Advanced DSU

Day 14 (2h): Review & Mixed Practice Revisit starred problems you found challenging.

Week 3-4: Advanced Patterns & Hard Problems

Day 15-16 (4h): Cycle Detection & Bridges

Critical Connections in a Network
Practice writing Tarjan's algorithm from memory

Day 17-19 (6h): Hard Shortest Path

Day 20-21 (4h): Hard Graph Construction

Day 22-24 (6h): Mixed Hard + Timed Practice

Select 2-3 hard problems daily
Time yourself: 45-60 minutes per problem
Focus on explaining your approach before coding

Day 25-28: Mock Interviews Use Thita.ai's AI interview mode for full 45-minute sessions, mixing graph problems with other patterns.

Total commitment: ~35-40 hours over 4 weeks

Common Graph Traversal Pitfalls

Even experienced engineers stumble on these. Here's how to avoid them:

⚠️ Forgetting to Mark Nodes as Visited in BFS/DFS Problem: Your recursion or queue enters infinite loops because nodes are revisited. Solution: Use a visited set or mark nodes in-place (if allowed). For DFS, mark before recursing; for BFS, mark when adding to the queue.

PYTHON
# Correct BFS
visited.add(start)
queue.append(start)
# NOT after popping from queue

⚠️ Choosing DFS When BFS is Required (or Vice Versa) Problem: You use DFS for shortest path in an unweighted graph, giving wrong results. Solution: BFS guarantees shortest path in unweighted graphs. DFS is for connectivity, cycle detection, or topological sort. Know which tool fits the job.

⚠️ Not Handling Disconnected Graphs Problem: You start traversal from one node and miss entire components. Solution: Loop over all nodes, running DFS/BFS from unvisited nodes.

PYTHON
for node in range(n):
    if node not in visited:
        dfs(node)

⚠️ Incorrect Cycle Detection in Directed Graphs Problem: Using a simple visited set for directed graphs misidentifies back edges. Solution: Use a recursion stack (or "on_path" set) to track nodes in the current DFS path.

⚠️ Forgetting Path Compression in Union-Find Problem: Your DSU runs in O(N) instead of nearly O(1), causing TLE on large inputs. Solution: Always implement path compression in your find() function.

⚠️ Building Adjacency List Incorrectly Problem: For undirected graphs, you only add edge u→v but not v→u, breaking connectivity. Solution: For undirected edges, add both directions:

PYTHON
graph[u].append(v)
graph[v].append(u)

⚠️ Misunderstanding Dijkstra's Priority Queue Problem: Using a regular queue or not handling duplicate entries correctly. Solution: Use a min-heap (priority queue) with (distance, node) tuples. Skip nodes if we've already found a shorter path.

Why Graph Traversal Beats Brute Force

Let's see the power of BFS for shortest path using Shortest Path in Binary Matrix:

Brute Force (DFS All Paths)

PYTHON
# Try all possible paths - Exponential time
def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n-1][n-1]:
        return -1

    min_path = [float('inf')]

    def dfs(r, c, path_len, visited):
        if r == n-1 and c == n-1:
            min_path[0] = min(min_path[0], path_len)
            return

        # Try all 8 directions
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < n and 0 <= nc < n and
                grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                dfs(nr, nc, path_len + 1, visited)
                visited.remove((nr, nc))

    dfs(0, 0, 1, {(0,0)})
    return min_path[0] if min_path[0] != float('inf') else -1

Time Complexity: O(8^(N²)) - Exponential! Tries every possible path.

BFS Shortest Path

PYTHON
from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n-1][n-1]:
        return -1

    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}

    directions = [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]

    while queue:
        r, c, dist = queue.popleft()

        if r == n-1 and c == n-1:
            return dist

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < n and 0 <= nc < n and
                grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

    return -1

Time Complexity: O(N²) - Each cell visited once Space Complexity: O(N²) - Queue and visited set

The Insight: BFS explores level by level, guaranteeing the first time we reach the target is the shortest path. DFS explores depth-first, potentially checking exponentially many paths before finding the shortest.

Beyond LeetCode: Real-World Applications

Graph traversal powers critical systems at the world's largest tech companies:

1. Social Network Analysis (Facebook, LinkedIn) Graph DFS/BFS finds mutual friends, suggests connections, and detects communities. Union-Find groups users into networks for friend recommendations.

2. Maps & Navigation (Google Maps, Uber) Dijkstra's and A* algorithms (BFS variant) compute fastest routes considering traffic, tolls, and road closures in real-time.

3. Network Infrastructure (AWS, Google Cloud) Critical Connections (bridges) identify network points whose failure would partition the system. MST algorithms optimize cable/fiber layouts to minimize cost.

4. Dependency Resolution (npm, pip, Maven) Topological sort orders package installations so dependencies are satisfied. Cycle detection prevents circular dependencies from breaking builds.

5. Recommendation Systems (Netflix, Amazon) Collaborative filtering uses graph traversal to find similar users/items. BFS explores "users who liked this also liked..." relationships.

Conclusion: From Confusion to Confidence

Graph traversal isn't a single technique—it's a toolkit of 11 powerful patterns that unlock solutions to some of the hardest interview problems. Master these patterns, and you'll approach graphs with the confidence of a seasoned engineer.

Key Takeaways:

BFS for shortest paths, level-order, and bidirectional search
DFS for connectivity, cycles, and topological sort
Dijkstra for weighted shortest paths
Union-Find for dynamic connectivity and grouping
Choose the right tool for the job—and explain why

Next Steps:

Remember: Graphs aren't scary when you know the patterns. Start with foundations, build systematically, and soon you'll be solving hard problems with ease.

External Resources

Ready to Master Graph Patterns?

At Thita.ai, we believe every engineer can conquer graph problems with the right guidance. Our AI-powered platform delivers personalized hints, instant feedback, and realistic mock interviews—all designed to help you master the patterns that matter at Google, Amazon, Meta, and beyond.

Don't just practice harder—practice smarter with pattern-based learning. Start mastering graph traversal now →

Master Graph Traversal Patterns (DFS & BFS): 11 templates for Coding Interviews

What You'll Learn

What is Graph Traversal Patterns (DFS & BFS)?

Why This Pattern Matters

The 11 Graph Traversal Patterns (DFS & BFS) Sub-Patterns

1. Bidirectional BFS (BFS Optimization for Known Source & Target)

2. Bridges & Articulation Points (Tarjan Low-Link)

3. Deep Copy / Cloning

4. Graph BFS – Connected Components / Island Counting

5. Graph BFS – Topological Sort (Kahn’s Algorithm)

6. Graph DFS – Connected Components / Island Counting

7. Graph DFS – Cycle Detection (Directed Graph)

8. Minimum Spanning Tree (Kruskal / Prim / DSU + Heap)

9. Shortest Path (Bellman-Ford / BFS+K)

10. Shortest Path (Dijkstra’s Algorithm)

11. Union-Find (Disjoint Set Union - DSU)

How to Master Graph Traversal Patterns on Thita.ai

Your Graph Traversal Learning Roadmap

Week 1: BFS & DFS Foundations (Days 1-7)

Week 2: Shortest Paths & Advanced BFS (Days 8-14)

Week 3-4: Advanced Patterns & Hard Problems

Common Graph Traversal Pitfalls

Why Graph Traversal Beats Brute Force

Brute Force (DFS All Paths)

BFS Shortest Path

Beyond LeetCode: Real-World Applications

Conclusion: From Confusion to Confidence

Related Articles

External Resources

Ready to Master Graph Patterns?

Topics

Related on Thita

Master DSA Patterns