Practice Graph Traversal Problems: 20+ Coding Exercises to Master BFS & DFS

If you’re serious about acing coding interviews or building efficient software, you need to practice graph traversal problems until they become second nature. Graphs power social networks, navigation apps, recommendation engines, and even compilers. Yet many students freeze when faced with a graph problem.

This comprehensive guide gives you a structured path to practice graph traversal problems effectively. You’ll get hands-on exercises, Python solutions, complexity analysis, and expert tips. Let’s turn graph anxiety into graph mastery.

Why You Must Practice Graph Traversal Problems Regularly

Graph traversal—visiting every vertex and edge in a systematic way—is the foundation of countless algorithms. Whether you’re performing a web crawl, finding the shortest path, or detecting cycles, traversal is your first step.

When you practice graph traversal problems consistently, you:

• Build muscle memory for BFS (Breadth-First Search) and DFS (Depth-First Search)
• Learn to choose the right traversal for the right scenario
• Spot common pitfalls like infinite loops or missed nodes

• Prepare for FAANG-style interview questions

  For a quick refresher on key graph concepts, check our Top Graph Algorithm Interview Questions & Answers.

Graph Representation: The Starting Point

Before you practice graph traversal problems, you must represent graphs in code. Two common ways:

Adjacency List (Most Popular)

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}

Adjacency Matrix

# For dense graphs
matrix = [
    [0, 1, 1, 0, 0, 0],
    [1, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 0, 1],
    # ... etc
]

For most traversal exercises, adjacency lists are simpler and more memory-efficient.

BFS Fundamentals: Level-by-Level Exploration

BFS uses a queue and processes vertices in order of their distance from the start. When you practice graph traversal problems with BFS, you’ll notice it’s perfect for:

• Shortest path in unweighted graphs
• Finding connected components
• Web crawling
• Social network friend suggestions

BFS Template

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

DFS Fundamentals: Deep Dive First

DFS uses a stack (or recursion) and goes as deep as possible before backtracking. Use DFS when you practice graph traversal problems involving:

• Detecting cycles
• Topological sorting
• Solving mazes
• Finding strongly connected components

Recursive DFS Template

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex, end=" ")

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

Iterative DFS Template

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=" ")
            # Add neighbors in reverse order for original order
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

Beginner Practice Graph Traversal Problems (Level 1)

Start here if you’re new to graphs. These exercises focus on basic traversal patterns.

Problem 1: Print All Nodes Reachable from a Given Start

Difficulty: Easy
Goal: Use BFS or DFS to visit every node in a connected component.

def reachable_nodes(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])
    return visited

# Test
graph = {0: [1,2], 1: [0,3], 2: [0], 3: [1]}
print(reachable_nodes(graph, 0))  # {0,1,2,3}

Problem 2: Detect if a Graph is Connected

Difficulty: Easy
Goal: Check if all nodes are reachable from any start node.

def is_connected(graph):
    if not graph:
        return True
    start = next(iter(graph))
    reachable = reachable_nodes(graph, start)
    return len(reachable) == len(graph)

Problem 3: Count Connected Components in Undirected Graph

Difficulty: Easy-Medium
Goal: Find how many separate clusters exist.

def count_components(graph):
    visited = set()
    components = 0

    for node in graph:
        if node not in visited:
            components += 1
            # BFS/DFS to mark all nodes in this component
            queue = [node]
            visited.add(node)
            while queue:
                curr = queue.pop(0)
                for neighbor in graph[curr]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
    return components

 

💡 Pro Tip: These beginner problems are the building blocks. Master them before moving on.

 

Intermediate Graph Traversal Exercises (Level 2)

Once basic traversal feels comfortable, level up with these challenges. When you practice graph traversal problems at intermediate difficulty, you’ll combine traversal with other techniques.

Problem 4: Find Shortest Path in Unweighted Graph (BFS)

Difficulty: Medium
Goal: Return the minimum number of edges between two nodes.

from collections import deque

def shortest_path(graph, start, target):
    if start == target:
        return [start]

    visited = {start: None}  # Stores parent pointers
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited[neighbor] = vertex
                if neighbor == target:
                    # Reconstruct path
                    path = []
                    while neighbor is not None:
                        path.append(neighbor)
                        neighbor = visited[neighbor]
                    return path[::-1]
                queue.append(neighbor)
    return None  # No path exists

Problem 5: Detect Cycle in Directed Graph (DFS with States)

Difficulty: Medium
Goal: Return True if the graph contains a cycle.

def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        if color[node] == GRAY:
            return True  # Cycle detected
        if color[node] == BLACK:
            return False

        color[node] = GRAY
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    return False

Problem 6: Topological Sort (DFS-based)

Difficulty: Medium
Goal: Order nodes so that for every edge u→v, u comes before v.

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]  # Reverse for correct order

Problem 7: Course Schedule (LeetCode 207)

Difficulty: Medium
Goal: Can you finish all courses given prerequisites? This is cycle detection.

def can_finish(num_courses, prerequisites):
    # Build graph
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # Same cycle detection as Problem 5
    return not has_cycle_directed(graph)

Problem 8: Flood Fill (LeetCode 733)

Difficulty: Easy-Medium
Goal: Change connected cells of the same color. Classic DFS/BFS on grid.

def flood_fill(image, sr, sc, new_color):
    original = image[sr][sc]
    if original == new_color:
        return image

    rows, cols = len(image), len(image[0])
    stack = [(sr, sc)]

    while stack:
        r, c = stack.pop()
        if image[r][c] == original:
            image[r][c] = new_color
            # Check 4-directional neighbors
            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 and image[nr][nc] == original:
                    stack.append((nr, nc))
    return image

Advanced Graph Traversal Challenges (Level 3)

Ready for serious interview prep? These problems require combining traversal with advanced concepts. As you practice graph traversal problems at this level, focus on optimizing time and space.

Problem 9: Word Ladder (LeetCode 127)

Difficulty: Hard
Goal: Find shortest transformation sequence from beginWord to endWord, changing one letter at a time.

from collections import deque

def ladder_length(begin_word, end_word, word_list):
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    queue = deque([(begin_word, 1)])  # (word, length)

    while queue:
        word, length = queue.popleft()
        if word == end_word:
            return length

        # Try changing each character
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in word_set:
                    word_set.remove(next_word)
                    queue.append((next_word, length + 1))
    return 0

Problem 10: Number of Islands (LeetCode 200)

Difficulty: Medium
Goal: Count connected components in a 2D grid.

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # Mark as visited
        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            dfs(r + dr, c + dc)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Problem 11: Clone Graph (LeetCode 133)

Difficulty: Medium
Goal: Deep copy an undirected graph.

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors else []

def clone_graph(node):
    if not node:
        return None

    old_to_new = {}

    def dfs(node):
        if node in old_to_new:
            return old_to_new[node]

        copy = Node(node.val)
        old_to_new[node] = copy

        for neighbor in node.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy

    return dfs(node)

Problem 12: Pacific Atlantic Water Flow (LeetCode 417)

Difficulty: Medium
Goal: Find cells that can flow to both Pacific and Atlantic oceans.

def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []

    rows, cols = len(heights), len(heights[0])
    pacific = set()
    atlantic = set()

    def dfs(r, c, ocean):
        ocean.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 and 
                (nr, nc) not in ocean and 
                heights[nr][nc] >= heights[r][c]):
                dfs(nr, nc, ocean)

    # Top and bottom edges
    for c in range(cols):
        dfs(0, c, pacific)
        dfs(rows-1, c, atlantic)

    # Left and right edges
    for r in range(rows):
        dfs(r, 0, pacific)
        dfs(r, cols-1, atlantic)

    return list(pacific & atlantic)

Real-World Applications to Motivate Your Practice

When you practice graph traversal problems, you’re not just preparing for interviews—you’re building real-world skills. For deeper context, read our article on Real-World Applications of Graph Traversal Algorithms.

Social Network Friend Suggestions (BFS)

BFS finds friends-of-friends efficiently. LinkedIn’s “People You May Know” uses a limited-depth BFS.

GPS Navigation (Dijkstra + BFS)

While Dijkstra handles weights, unweighted BFS gives the fewest turns. Google Maps uses variations.

Web Crawlers (DFS or BFS)

Search engines traverse the web graph, being careful not to revisit pages.

Garbage Collection (DFS)

Mark-and-sweep garbage collectors traverse object reference graphs.

Common Mistakes When You Practice Graph Traversal Problems

Even experienced developers slip up. Avoid these pitfalls:

1. Forgetting to Mark Visited Nodes

# WRONG: Infinite loop!
def bad_bfs(graph, start):
    queue = [start]
    while queue:
        node = queue.pop(0)
        queue.extend(graph[node])  # Never marks visited

2. Using Recursion for Deep Graphs

Python’s recursion limit (~1000) fails for large graphs. Use iterative DFS for production.

3. Confusing BFS and DFS Use Cases

• BFS: shortest path, level-order, social distance
• DFS: cycle detection, topological sort, backtracking

4. Incorrect Graph Representation

For sparse graphs, adjacency matrices waste memory (O(V²)). Use adjacency lists (O(V+E)).

How to Practice Graph Traversal Problems Efficiently

Follow this weekly plan to build lasting skills:

Week 1-2:

• Implement BFS and DFS from scratch daily
• Solve Problems 1-3 (connected components, reachability)
  Week 3-4:
• Focus on shortest path (Problem 4) and cycle detection (Problem 5)
• Practice on paper then code
  Week 5-6:
• Tackle intermediate problems (6-8)
• Time your solutions (aim for 20-30 minutes each)
  Week 7-8:
• Attack advanced problems (9-12)
• Review Top Graph Algorithm Interview Questions & Answers

Debugging Graph Traversals: Pro Techniques

When your traversal fails, use these strategies:

Print the Traversal Order

def bfs_with_logging(graph, start):
    visited = set()
    queue = [start]
    print(f"Starting BFS from {start}")
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            print(f"Visiting {node}, neighbors: {graph[node]}")
            queue.extend(graph[node])
    print(f"Final visited: {visited}")

Visualize Small Graphs

Draw the graph on paper and trace your algorithm manually.

Use Python’s pdb

import pdb; pdb.set_trace()  # Insert before suspect loop

For more debugging help, see our Debugging Python Code Like a Pro: Tips & Tricks.

Time Complexity Analysis for Graph Traversals

When you practice graph traversal problems, always analyze complexity:

AlgorithmTime ComplexitySpace ComplexityBFS (adjacency list)O(V + E)O(V)DFS (recursive)O(V + E)O(V) (call stack)DFS (iterative)O(V + E)O(V)BFS on gridO(R * C)O(R * C)Understanding Big O is crucial. Review our Mastering Time Complexity Analysis for Data Structures for deeper insights.

Recommended Learning Path After Mastering Graph Traversals

Once you can confidently practice graph traversal problems, expand into:

1. Shortest path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)
2. Minimum spanning trees (Prim’s, Kruskal’s)
3. Maximum flow (Ford-Fulkerson, Edmonds-Karp)
4. Strongly connected components (Tarjan’s, Kosaraju’s)
    

Also explore our related career guides:

• Career Development in Python Programming: Complete Guide
• Master Algorithm Implementation for Coding Interviews | Guide
• Dynamic Programming Interview Prep for Beginners

Frequently Asked Questions

Q1: How many graph traversal problems should I solve before an interview?

Aim for 30-40 well-chosen problems covering BFS, DFS, topological sort, cycle detection, and connected components. Quality matters more than quantity. Solve each problem 2-3 times without looking at solutions.

Q2: Should I memorize BFS and DFS code?

Yes, memorize the core templates (about 10-15 lines each). But understand why each line exists. During interviews, you can write the template from memory and adapt it to the problem.

Q3: How do I choose between BFS and DFS during an interview?

Ask yourself: “Do I need the shortest path or level-order information?” → BFS. “Am I in a deep graph with potential cycles or need backtracking?” → DFS. “Is the graph very wide?” → DFS might cause stack overflow, use BFS.

Q4: What’s the best language to practice graph traversal problems?

Python is excellent due to simple syntax, built-in deque for BFS, and readable code. Java and C++ are also common. Our examples use Python—see Top Python Learning Resources for Students (2026 Guide).

Q5: How do I handle weighted graphs in traversal?

Standard BFS/DFS don’t work directly for shortest path in weighted graphs. Use Dijkstra’s algorithm (priority queue BFS) or Bellman-Ford. However, DFS can still detect cycles in weighted directed graphs.

Conclusion

To truly practice graph traversal problems effectively, start with the basics, progress methodically, and never skip the debugging step. Graphs are everywhere in tech, and traversal is your entry point to solving complex problems.

Remember:

• BFS → Queue, level-order, shortest path (unweighted)
• DFS → Stack/recursion, depth-first, cycle detection
• Always track visited nodes to avoid infinite loops
• Choose the right representation (adjacency list wins most times)
   

Bookmark this guide and return to it as you level up. Combine these exercises with our Top Graph Algorithm Interview Questions & Answers for complete interview preparation.

Now open your editor and start coding. The graph won’t traverse itself!