BFS vs DFS: Choosing the Right Graph Traversal

Graph problems show up in technical interviews as scheduling tasks, dependency chains, or route planning. The word "graph" rarely appears in the problem statement.

The algorithms themselves aren't complicated. BFS, DFS, Dijkstra's, topological sort — each one takes maybe 20-30 lines of code. What trips people up is spending half the interview solving the wrong problem. They'll treat a graph as dynamic programming, or recognize the graph but reach for BFS when topological sort is needed. It is the graph's structure that determines which algorithm works. 

Before diving into traversal algorithms, you need to understand what graphs are and how they're structured.

Directed vs Undirected Graphs

In an undirected graph, edges have no direction. If node A connects to node B, then B connects to A. Think of Facebook friendships (mutual connection) or road systems (you can drive both ways).

In a directed graph (digraph), edges have direction. An edge from A to B doesn't mean an edge from B to A exists. Think of Twitter follows (you can follow someone who doesn't follow you back) or one-way streets.

Weighted vs Unweighted Graphs

In an unweighted graph, all edges are equal. Moving from any node to its neighbor costs the same. Think of counting friend connections (each connection counts as 1).

In a weighted graph, edges have values (weights). Moving from node A to node B might cost 5, while A to C costs 10. Think of road networks (different distances between cities) or task durations (some tasks take longer than others).

Connected vs Disconnected Graphs

A connected graph means you can reach any node from any other node by following edges. A disconnected graph has separate components with no paths between them. Think of separate social network groups with no mutual friends.

Cycles

A cycle exists when you can start at a node, follow edges, and return to the starting node. Undirected graphs naturally have cycles (A-B-C-A). Directed graphs might have cycles (A→B→C→A) or be acyclic (no way to loop back).

A Directed Acyclic Graph (DAG) is a directed graph with no cycles. Critical for dependency systems where cycles would create impossible situations (Task A requires Task B which requires Task A).

How graphs are represented in code

You can store graphs two main ways. Each has tradeoffs affecting your algorithm's performance.

Adjacency List

Store each node with a list of its neighbors. Most common representation because it's space-efficient for sparse graphs (graphs with relatively few edges).

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

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

Adjacency Matrix

Store a 2D array where matrix[i][j] indicates if an edge exists from node i to node j. For weighted graphs, store the weight instead of 1. Use 0 or infinity to indicate no edge.

# Example: same graph as above, unweighted
# 1 means edge exists, 0 means no edge
matrix = [
    [0, 1, 1, 0],  # Node 0 connects to 1 and 2
    [1, 0, 1, 1],  # Node 1 connects to 0, 2, and 3
    [1, 1, 0, 1],  # Node 2 connects to 0, 1, and 3
    [0, 1, 1, 0]   # Node 3 connects to 1 and 2
]

# For weighted graphs
weighted_matrix = [
    [0, 4, 1, float('inf')],
    [4, 0, 2, 5],
    [1, 2, 0, 8],
    [float('inf'), 5, 8, 0]
]

Which representation to use?

Adjacency list is better when the graph is sparse (few edges relative to nodes), you need to iterate through neighbors frequently, memory is constrained, or space complexity matters (O(V + E) vs O(V²)).

An adjacency matrix is better when the graph is dense (many edges), you need to check if a specific edge exists (O(1) lookup), implementing algorithms that need random edge access, or working with mathematical operations on graphs.

For most interview problems and production systems, adjacency lists are the best choice because real-world graphs tend to be sparse. Social networks, web pages, and task dependencies all have far fewer edges than the theoretical maximum.

Quick comparison table

Here's how the three main graph traversal algorithms compare.

Understanding Depth-First Search (DFS)  

DFS goes deep before going wide. Start at a node, pick an unvisited neighbor, keep going until you hit a dead end, then backtrack. You can implement it recursively (using the call stack) or iteratively (with an explicit stack).

Recursive approach

The recursive implementation feels natural because it mirrors how we think about exploring paths. Start at a node, mark it visited, then recursively explore each unvisited neighbor. The call stack handles backtracking automatically when you hit dead ends.

function DFS(node):
    mark node as visited
    for each neighbor of node:
        if neighbor not visited:
            DFS(neighbor)

Iterative approach

The iterative version gives you more control and avoids stack overflow on deep graphs. Use an explicit stack data structure instead of the call stack.

function DFS_iterative(start):
    create empty stack
    push start onto stack
    
    while stack not empty:
        node = pop from stack
        if node not visited:
            mark node as visited
            for each neighbor of node:
                if neighbor not visited:
                    push neighbor onto stack

The key detail? Mark nodes as visited when you start processing them, not when you finish. This prevents cycles from causing infinite loops. If you wait to mark nodes until after processing, you'll revisit nodes multiple times in graphs with cycles.

For annotation graphs, DFS means processing one complete review chain before starting the next. Worker A annotates item 1. Worker B reviews A's work on item 1. Worker C validates B's review of item 1. Chain complete. Start item 2.

This catches mistakes immediately. If Worker A misunderstands the rubric on item 1, Worker B flags it during review. One error, immediate correction, 99 remaining items protected.

When to use DFS

DFS works best for several specific scenarios.

• Cycle detection: Finding circular dependencies in graphs. Check if you encounter a node that's still in your current recursion stack. A classic use case is detecting deadlocks in resource allocation or circular dependencies in build systems.
• Pathfinding with detailed route tracking: When you need the actual path, not just whether one exists. DFS naturally tracks the path from the start to the current node through the recursion or explicit stack.
• Topological sorting in DAGs: Ordering nodes so all dependencies come before dependents. Used for course prerequisites, task scheduling, and build order determination.
• Connected components: Identifying separate subgraphs in an undirected graph. Run DFS from each unvisited node to find all nodes in that component.
• The target is likely far from the start: if your solution is near leaf nodes (far from the root), DFS reaches it without exploring all the shallow nodes first.
• High branching factor with limited memory. DFS only stores the current path (depth of tree) and not the entire levels (width of tree). Better memory profile when graphs are wide but not deep.
• Production annotation use case: Multi-stage review pipelines where each stage depends on the previous stage being correct. Quality measurement happens at every node. Errors surface before propagating to the next batch.

Common DFS mistakes

• Forgetting to track visited nodes: Without tracking visited nodes, you'll loop infinitely in graphs with cycles. Always maintain a visited set or array and check it before processing each node.
• Not handling disconnected graphs: Starting DFS from one node only explores that connected component. For graphs with multiple components, iterate through all nodes and start a new DFS for any unvisited ones. This is especially important in annotation systems where different worker clusters might be disconnected from each other.
• Recursion depth issues: Recursive DFS can blow the call stack on graphs with long paths. If your graph might go thousands of nodes deep, switch to iterative with an explicit stack. Python's default recursion limit is around 1,000. Hit that, and your program crashes.
• Using the wrong data structure: DFS requires a stack (LIFO, last in, first out). If you accidentally use a queue, you've implemented BFS instead. The traversal order completely changes.
• Marking nodes at the wrong time: Mark nodes as visited when you start processing them, not when you finish. If you mark after finishing, cycles will cause you to process nodes multiple times before marking them.

Understanding Breadth-First Search (BFS)

BFS explores neighbors before going deeper. Visit all nodes one hop away, then all nodes two hops away, then three hops, and so on. Uses a queue (FIFO, first in first out) to maintain this level-by-level ordering.

How BFS works

Start by adding the root node to a queue and marking it visited. Then repeatedly remove the front node from the queue, process it, and add all its unvisited neighbors to the back of the queue (marking them visited immediately). Continue until the queue empties.

function BFS(start):
    create empty queue
    add start to queue
    mark start as visited
    
    while queue not empty:
        node = remove front of queue
        process node
        
        for each neighbor of node:
            if neighbor not visited:
                mark neighbor as visited
                add neighbor to queue

The critical detail? Mark nodes visited when you add them to the queue, not when you remove them. If you wait until removal, the same node can get added multiple times before you process it once. That wastes memory and creates duplicates.

BFS guarantees you'll find the shortest path in unweighted graphs because it explores by distance. When you first reach a target node, you've found it via the minimum number of edges.

In annotation graphs, BFS means processing all items at a single stage before moving to the next. Worker A annotates all 100 items. After A finishes completely, Worker B reviews all 100 of A's annotations. After B finishes completely, Worker C validates all 100 of B's reviews.

This delays error detection. If Worker A misunderstands the rubric, you don't discover it until Worker B has reviewed all 100 items incorrectly. One hundred errors are created before anyone catches the pattern.

When to use BFS

BFS works best for specific scenarios.

• Shortest path in unweighted graphs: BFS guarantees finding the minimum number of edges between two nodes. The first time you reach the target, you've found the shortest path. Used in navigation systems, social network "degrees of separation," and puzzle solvers.
• Level-order traversal: Processing nodes by their distance from the start. Each "level" represents nodes at distance k from the source. Used in tree printing, organizational hierarchy traversal, and network broadcast simulation.
• Connected components in undirected graphs: Similar to DFS, but BFS can also give you the shortest path to each node in the component. Run BFS from each unvisited node to group connected nodes.
• Target likely near start: If your solution is probably close to the starting point, BFS finds it without exploring the entire deep structure. Saves time when graphs are deep but solutions are shallow.
• Finding "all paths of length k":  BFS naturally processes nodes at exact distances. Easy to find all nodes exactly k edges away from the start.
• Production annotation use case: Initial screening where batch processing enables statistical quality checks. Process 1,000 annotations, run inter-annotator agreement metrics, identify outliers, and reject the batch if agreement is too low. The batch approach works when quality is measurable through statistics rather than chain-of-dependency validation.

Common BFS problems

• Marking nodes visited too late: The most common BFS bug. Mark nodes as visited when adding them to the queue, not when removing them. Otherwise, the same node gets enqueued multiple times before you process it once. This wastes memory and creates duplicate work.
• Inefficient queue operations: Using arrays with shift/unshift (or pop(0)) creates O(n) overhead per operation. Use actual queue data structures (collections.deque in Python, Queue in Java) that provide O(1) enqueue and dequeue.
• Forgetting to track distance: If you need the actual distance to each node, maintain a distance array or store (node, distance) tuples in the queue. Don't try to calculate it after the fact. Track it during traversal.
• Not handling multiple sources: Some problems require starting BFS from multiple nodes simultaneously. Push all source nodes into the queue initially before starting the main loop.
• Memory issues on wide graphs: BFS stores all nodes at the current level in memory. On very wide graphs (high branching factor), this can consume significant memory. Be aware of the width of your graph structure.

The Third Type: Topological Sort

Topological sort arranges vertices in a directed acyclic graph (DAG) so that for every directed edge from vertex u to vertex v, u appears before v in the ordering. Think course prerequisites. Calculus I must come before Calculus II in your schedule.

Unlike DFS or BFS which work on any graph, topological sort has strict requirements. The graph must be directed (edges have direction) and acyclic (no cycles). If your graph has cycles or undirected edges, topological sorting won't work.

What topological sort does

There are two common approaches.

Kahn's Algorithm (BFS approach)

This uses in-degree (the number of incoming edges) to determine the ordering. Nodes with zero in-degree have no dependencies and can be processed first.

function topological_sort_kahns(graph):
    calculate in-degree for each vertex
    create empty queue
    create empty result list
    
    // Add all vertices with in-degree 0 to queue
    for each vertex:
        if in_degree[vertex] == 0:
            add vertex to queue
    
    while queue not empty:
        vertex = remove front of queue
        add vertex to result
        
        // Reduce in-degree for neighbors
        for each neighbor of vertex:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                add neighbor to queue
    
    if result.length != number of vertices:
        return "Graph has cycle"
    return result

DFS-based approach

This uses the finishing time of nodes during DFS. Nodes that finish later (no more neighbors to explore) should come earlier in the topological order.

function topological_sort_dfs(graph):
    create empty stack
    create visited set
    
    function dfs(vertex):
        mark vertex as visited
        for each neighbor of vertex:
            if neighbor not visited:
                dfs(neighbor)
        // Push to stack after visiting all neighbors
        push vertex onto stack
    
    for each vertex in graph:
        if vertex not visited:
            dfs(vertex)
    
    // Stack now contains vertices in topological order
    return stack (popped in order)

‍

Kahn's algorithm is easier to understand and naturally detects cycles. If you can't process all the vertices, there's a cycle. The DFS approach is more elegant for recursion enthusiasts and integrates well if you're already using DFS for other purposes.

Where topological sort gets used

• Course prerequisite planning: Universities use this to schedule courses. If Data Structures requires Intro to Programming, topological sort ensures students take Intro first. Works for complex prerequisite chains with multiple dependencies.
• Task scheduling in project management: Break projects into tasks with dependencies. "Install foundation before framing walls." Topological sort gives you a valid execution order. Critical for construction, software builds, manufacturing processes.
• Package manager dependency resolution: Tools like npm, pip, and Maven use topological sorting. If Package X depends on Package Y which depends on Package Z, the sort ensures you install Z, then Y, then X. Prevents "dependency not found" errors.
• Build systems: Compiling code with interdependent modules. File A imports File B, which imports File C. Topological sort determines compilation order. This is why Makefiles and build tools can handle complex dependency graphs.
• Database operations: When managing foreign key constraints, databases use topological sorting for bulk inserts or deletions. Ensures you don't try to insert a child record before its parent exists.

Choosing between DFS, BFS, and topological sort

Most problems can technically be solved with either DFS or BFS. Both visit all nodes, both run in O(V+E) time. But the right choice depends on what you're trying to find and when you need to find it. Here are the main differences between these graph traversing methods:

Traversal pattern

• DFS goes deep (explore one path fully before backtracking)
• BFS goes wide (explore all neighbors before going deeper)
• Topological sort orders by dependencies (not just traversal)

Data structure

• DFS uses stack (LIFO), explicit stack or recursion
• BFS uses queue (FIFO), always explicit queue
• Topological uses queue (Kahn's) or stack (DFS-based)

Memory usage

• DFS stores current path (depth of graph)
• BFS stores current level (width of graph)
• Topological stores in-degrees plus queue, O(V)

Path guarantees

• DFS finds a path (not necessarily shortest)
• BFS finds shortest path in unweighted graphs
• Topological finds valid ordering (not about paths)

Decision framework

Choose DFS when you need to:

• Explore all possible paths (backtracking problems)
• Detect cycles (DFS naturally tracks recursion stack)
• Do topological sort on DAGs
• Find targets likely far from start (near leaves)
• Work with wide but not deep graphs (memory constrained)
• Get the actual path, not just the distance
• Measure quality at each dependency level

‍

Choose BFS when you need to:

• Find shortest path in unweighted graphs
• Locate targets likely near start (shallow search)
• Do level-order traversal
• Process nodes by distance from source
• Start from multiple points with parallel exploration
• Work with deep but not wide graphs
• Measure quality through batch statistics

​​https://stackoverflow.com/questions/3332947/what-are-the-practical-factors-to-consider-when-choosing-between-depth-first-sea

‍

Choose Topological Sort when you need to:

• Work with DAGs (directed, no cycles)
• Solve dependency or ordering problems
• Schedule courses, plan tasks, and determine build orders
• Process items so dependencies come first
• Detect if cycles exist (Kahn's algorithm fails on cycles)

Apply your technical expertise at DataAnnotation

If your background includes technical expertise, domain knowledge, or the critical thinking to evaluate complex trade-offs, such as choosing the right graph traversal algorithm for production systems, AI training at DataAnnotation means contributing directly to AGI development.

Getting from interested to earning takes five straightforward steps:

1. Visit the DataAnnotation application page and click "Apply"
2. Complete the brief form with your background and technical expertise
3. Take the Coding Starter Assessment (approximately 1-2 hours)
4. Watch for the approval decision, typically within a few days
5. Log into your dashboard, select projects matching your skills, and begin contributing

No signup fees. DataAnnotation stays selective to maintain quality standards. You can only take the Starter Assessment once, so read the instructions carefully and review before submitting.

Apply to DataAnnotation if you understand why expert evaluation shapes AI capabilities and you have the technical depth to contribute.