Graph Algorithms Tutorial: Master BFS, DFS & Topological Sort for Interviews

When Graphs Finally Clicked for Me

Graph problems used to intimidate me more than any other topic. The moment I saw "graph" in a problem description, my confidence plummeted. There were so many concepts—BFS, DFS, cycles, topological sort, shortest paths, connected components—and I had no framework to know which to use when.

Then I realized: most graph problems use one of just 4 core patterns. Once I learned to recognize these patterns, graph problems became systematic. I wasn't guessing anymore—I was pattern matching.

In this guide, I'll share the exact framework that transformed graphs from my weakness to one of my interview strengths. You'll learn when to use BFS vs DFS, how to detect cycles, and the templates that solve 90% of graph problems.

Understanding Graphs: More Than Just Trees

A graph is nodes (vertices) connected by edges. Unlike trees:

• Can have cycles (a path from a node back to itself)
• Can be disconnected (multiple separate components)
• Edges can be directed (one-way) or undirected (two-way)
• Edges can have weights (costs/distances)

Graph representations:

# 1. Adjacency List (most common for interviews)
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

# 2. Adjacency Matrix (good for dense graphs)
graph = [
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [1, 0, 0, 1],
    [0, 0, 0, 1]
]

# 3. Edge List (simple but less efficient)
edges = [(0,1), (0,2), (1,2), (2,0), (2,3), (3,3)]

For interviews, adjacency list is almost always the best choice.

The Four Core Graph Patterns

Pattern 1: Breadth-First Search (BFS)

When to use BFS:

• Finding shortest path in unweighted graphs
• Level-by-level exploration
• "Minimum steps/moves" problems
• Finding closest nodes

The BFS template:

from collections import deque

def bfs_template(graph, start):
    """
    BFS template using queue.
    Explores level by level.
    """
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()

        # Process node
        process(node)

        # Add unvisited neighbors to queue
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Key insight: BFS uses a queue (FIFO). We visit all nodes at distance k before visiting any node at distance k+1. This guarantees shortest path.

Example: Shortest Path in Unweighted Graph

def shortest_path(graph, start, end):
    """
    Find shortest path from start to end.
    Track parent to reconstruct path.
    """
    if start == end:
        return [start]

    visited = {start}
    queue = deque([(start, [start])])  # (node, path)

    while queue:
        node, path = queue.popleft()

        for neighbor in graph[node]:
            if neighbor == end:
                return path + [neighbor]

            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return []  # No path found

Example: Number of Islands (BFS)

LeetCode #200 - Number of Islands

def num_islands(grid):
    """
    Count islands using BFS.
    Each BFS explores one complete island.
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def bfs(r, c):
        """BFS to mark entire island as visited."""
        queue = deque([(r, c)])
        visited.add((r, c))

        while queue:
            row, col = queue.popleft()

            # Check all 4 directions
            directions = [(0,1), (1,0), (0,-1), (-1,0)]
            for dr, dc in directions:
                nr, nc = row + dr, col + dc

                if (0 <= nr < rows and 0 <= nc < cols and
                    grid[nr][nc] == '1' and (nr, nc) not in visited):
                    visited.add((nr, nc))
                    queue.append((nr, nc))

    # Try starting BFS from each unvisited land cell
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1' and (i, j) not in visited:
                bfs(i, j)
                islands += 1

    return islands

Key insight: Each BFS explores one complete connected component (island). Count how many times we start a new BFS.

Pattern 2: Depth-First Search (DFS)

When to use DFS:

• Exploring all paths
• Cycle detection
• Backtracking through graphs
• Connected components
• Problems that don't need shortest path

The DFS template (recursive):

def dfs_template(graph, node, visited):
    """
    DFS template using recursion.
    Explores deeply before backtracking.
    """
    if node in visited:
        return

    visited.add(node)

    # Process node
    process(node)

    # Recurse on neighbors
    for neighbor in graph[node]:
        dfs_template(graph, neighbor, visited)

DFS template (iterative with stack):

def dfs_iterative(graph, start):
    """
    DFS using explicit stack.
    Useful when recursion depth is a concern.
    """
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()

        if node in visited:
            continue

        visited.add(node)
        process(node)

        # Add neighbors to stack
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

Example: Detect Cycle in Directed Graph

def has_cycle_directed(graph, n):
    """
    Detect cycle in directed graph using DFS.
    Track nodes in current recursion stack.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(node):
        """
        WHITE: unvisited
        GRAY: in current path (recursion stack)
        BLACK: completely processed
        """
        if color[node] == GRAY:
            return True  # Back edge found = cycle!

        if color[node] == BLACK:
            return False  # Already processed

        # Mark as in current path
        color[node] = GRAY

        # Check all neighbors
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True

        # Mark as completely processed
        color[node] = BLACK
        return False

    # Check all nodes (graph might be disconnected)
    for node in range(n):
        if color[node] == WHITE:
            if dfs(node):
                return True

    return False

Key insight: We use three colors:

• White: Unvisited
• Gray: In current DFS path (on recursion stack)
• Black: Completely explored

If we encounter a GRAY node, we've found a back edge → cycle!

Example: All Paths from Source to Target

def all_paths_source_target(graph, source, target):
    """
    Find all paths from source to target.
    Classic DFS with backtracking.
    """
    result = []

    def dfs(node, path):
        # Reached target
        if node == target:
            result.append(path[:])
            return

        # Try all neighbors
        for neighbor in graph[node]:
            path.append(neighbor)
            dfs(neighbor, path)
            path.pop()  # Backtrack

    dfs(source, [source])
    return result

Key insight: DFS naturally explores all paths. We use backtracking (add node, recurse, remove node) to try different paths.

Pattern 3: Topological Sort

When to use:

• Directed Acyclic Graph (DAG) problems
• Dependency resolution (course prerequisites, build systems)
• Scheduling with constraints
• Keywords: "order," "prerequisites," "dependencies"

What is topological sort? A linear ordering of nodes such that for every directed edge u → v, u comes before v.

Only works on DAGs (if there's a cycle, no valid ordering exists).

Method 1: DFS-based (Postorder)

def topological_sort_dfs(graph, n):
    """
    Topological sort using DFS.
    Add nodes to result in postorder (after exploring all descendants).
    """
    visited = [False] * n
    result = []

    def dfs(node):
        visited[node] = True

        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)

        # Add after exploring all descendants
        result.append(node)

    # Process all nodes
    for node in range(n):
        if not visited[node]:
            dfs(node)

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

Method 2: Kahn's Algorithm (BFS-based)

from collections import deque

def topological_sort_kahns(graph, n):
    """
    Topological sort using Kahn's algorithm (BFS).
    Process nodes with 0 in-degree first.
    """
    # Calculate in-degrees
    in_degree = [0] * n
    for node in range(n):
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # Start with nodes that have 0 in-degree
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        # Reduce in-degree of neighbors
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If result doesn't include all nodes, graph has cycle
    return result if len(result) == n else []

Example: Course Schedule

LeetCode #207 - Course Schedule

def can_finish(num_courses, prerequisites):
    """
    Check if all courses can be finished given prerequisites.
    This is cycle detection in directed graph!
    """
    # Build adjacency list
    graph = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # Calculate in-degrees
    in_degree = [0] * num_courses
    for course in range(num_courses):
        for next_course in graph[course]:
            in_degree[next_course] += 1

    # Kahn's algorithm
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1

        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return completed == num_courses

Key insight: If we can process all courses (topological sort succeeds), there's no cycle. If there's a cycle, some courses will never have in-degree 0.

Pattern 4: Union-Find (Disjoint Set Union)

When to use:

• Dynamic connectivity (are nodes connected?)
• Cycle detection in undirected graphs
• Number of connected components
• Kruskal's minimum spanning tree
• Problems where you're joining sets

The Union-Find template:

class UnionFind:
    """
    Union-Find data structure with path compression and union by rank.
    Efficiently handles connectivity queries.
    """

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        """Find root with path compression."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        """Union by rank."""
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False  # Already connected

        # Union by rank: attach smaller tree under larger
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

        self.components -= 1
        return True

    def connected(self, x, y):
        """Check if x and y are in same component."""
        return self.find(x) == self.find(y)

Time complexity: Nearly O(1) per operation (amortized α(n), where α is inverse Ackermann function)

Example: Number of Connected Components

def count_components(n, edges):
    """
    Count connected components using Union-Find.
    """
    uf = UnionFind(n)

    for u, v in edges:
        uf.union(u, v)

    return uf.components

Example: Redundant Connection (Cycle Detection)

LeetCode #684 - Redundant Connection

def find_redundant_connection(edges):
    """
    Find edge that creates cycle in undirected graph.
    Use Union-Find: if union fails, edge creates cycle.
    """
    n = len(edges)
    uf = UnionFind(n + 1)

    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # This edge creates cycle

    return []

Key insight: In Union-Find, if we try to union two nodes that are already in the same set, adding that edge would create a cycle.

BFS vs DFS: The Decision Matrix

Rule of thumb:

• Need shortest path? → BFS
• Need all paths or backtracking? → DFS
• Need dynamic connectivity? → Union-Find

Common Graph Pitfalls

Mistake 1: Forgetting Disconnected Components

# WRONG: Only explores from node 0
visited = set()
dfs(graph, 0, visited)

# RIGHT: Check all nodes
visited = set()
for node in range(n):
    if node not in visited:
        dfs(graph, node, visited)

Mistake 2: Not Tracking Visited in BFS/DFS

# WRONG: Infinite loop possible
queue = [start]
while queue:
    node = queue.pop(0)
    for neighbor in graph[node]:
        queue.append(neighbor)  # Revisits nodes!

# RIGHT: Track visited
visited = {start}
queue = [start]
while queue:
    node = queue.pop(0)
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

Mistake 3: Confusing Directed vs Undirected

In undirected graphs, if there's an edge (u, v), both u→v and v→u exist. Build graph accordingly:

# Undirected graph
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # Add both directions!

Mistake 4: Wrong Cycle Detection Method

For directed graphs: Use DFS with three colors For undirected graphs: Use Union-Find or DFS with parent tracking

The Graph Problem Decision Tree

When you see a graph problem:

1. What type of graph?

• Directed or undirected?
• Weighted or unweighted?
• DAG or cyclic?

2. What are you asked to find?

• Shortest path → BFS or Dijkstra (if weighted)
• All paths → DFS with backtracking
• Cycle → DFS (directed) or Union-Find (undirected)
• Connected components → DFS, BFS, or Union-Find
• Topological order → DFS or Kahn's (must be DAG)

3. Are edges being added dynamically?

• YES → Union-Find
• NO → BFS or DFS

My Practice Strategy

Here's how I mastered graphs:

Week 1: Master BFS and DFS

• Implement both from scratch 10 times
• Solve shortest path, all paths, connected components
• 15-20 problems

Week 2: Cycle Detection and Topological Sort

• Cycle detection in directed and undirected graphs
• Both topological sort methods
• Course schedule variations
• 10-15 problems

Week 3: Union-Find

• Implement Union-Find with optimizations
• Connected components, redundant connection
• 10-15 problems

Week 4: Mixed and Advanced

• 30-40 problems mixing all patterns
• Practice pattern recognition
• Timed practice: identify pattern in 1 minute

Real Interview Success

I was asked: "Given a list of equations like a/b = 2.0, answer queries like a/c = ?"

My thought process:

1. "Build graph where nodes are variables, edges are division relationships"
2. "Query is finding path between two nodes"
3. "Multiply edge weights along path" → weighted BFS/DFS

Coded in 18 minutes using DFS with path tracking.

Key insight: Many problems disguise graph problems. Look for:

• Relationships between entities
• Dependencies
• State transitions

Conclusion: Your Graph Mastery Roadmap

Graphs aren't as intimidating as they seem. Here's what matters:

1. Master BFS and DFS first - Core building blocks
2. Learn when to use which - Shortest path vs all paths
3. Understand topological sort - Critical for DAG problems
4. Practice Union-Find - Efficient for connectivity
5. Recognize graph problems - Not always obvious

Start with BFS and DFS on simple problems. Once comfortable, move to cycle detection and topological sort. Finally, learn Union-Find for dynamic connectivity.

Within 4 weeks of focused practice, you'll recognize graph patterns instantly and code solutions confidently.

Remember: every graph expert once found BFS and DFS confusing. The difference is they practiced until the patterns became automatic.

Happy coding, and may your graphs always be acyclic!

If you found this guide helpful, share it with others learning algorithms. Graphs are everywhere in real systems—mastering them makes you a better problem solver. If this guide helped you master graph dsa, understand BFS/DFS, or solve graph interview questions, I'd love to hear about it! Connect with me on Twitter or LinkedIn.

Support My Work

If this guide helped you finally understand graph dsa, gave you confidence with BFS and DFS, or helped you ace graph interview questions, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.

☕ Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!

Cover image by Alina Grubnyak on Unsplash