Demystifying Graph Traversal: BFS vs. DFS and When to Use Which

Introduction
When solving graph problems in Data Structures and Algorithms (DSA), two fundamental search paradigms form the backbone of nearly every algorithm: Breadth-First Search (BFS) and Depth-First Search (DFS).
While both traverse every reachable node in a connected component, their traversal mechanics, memory usage patterns, and practical use cases differ significantly. Understanding these trade-offs is essential for selecting the optimal approach in technical problem-solving.

Breadth-First Search (BFS)
BFS explores a graph layer-by-layer, radiating outward from the source node. It visits all neighbors at distance k before visiting any nodes at distance k+1.

• Underlying Data Structure: FIFO Queue
• Time Complexity: O(V + E) (using an adjacency list)
• Space Complexity: O(V) (in the worst case, storing all leaf nodes)

void bfs(int startVertex, struct Node** adj, int totalVertices) {
    bool visited[totalVertices];
    for (int i = 0; i < totalVertices; i++) visited[i] = false;

    int queue[totalVertices];
    int front = 0, rear = 0;

    visited[startVertex] = true;
    queue[rear++] = startVertex;

    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        struct Node* temp = adj[current];
        while (temp != NULL) {
            int neighbor = temp->vertex;
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue[rear++] = neighbor;
            }
            temp = temp->next;
        }
    }
}

Best Used For:

• Finding the shortest path in unweighted graphs.
• Finding the nearest exit or level-order tree traversal.
• Cycle detection in undirected graphs.

Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It dives deep into the graph along one path until it hits a dead end, then backtracks to previous decision points.

• Underlying Data Structure: LIFO Stack (or the call stack via recursion)
• Time Complexity: O(V + E)
• Space Complexity: O(h) where h is the maximum recursion depth O(V) in the worst case for a linear graph)

void dfs(int current, struct Node** adj, bool visited[]) {
    visited[current] = true;
    printf("%d ", current);

    struct Node* temp = adj[current];
    while (temp != NULL) {
        int neighbor = temp->vertex;
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
        temp = temp->next;
    }
}

Best Used For:

• Topological sorting (e.g., Kahn’s algorithm or DFS finish-times).
• Detecting cycles in directed graphs (using recursion stack tracking).
• Finding strongly connected components (Kosaraju's / Tarjan's algorithms).
• Path existence problems where path length is not a constraint.

Conclusion
The choice between BFS and DFS comes down to the problem constraints. If your goal is to find the closest target, the shortest path, or evaluate immediate neighbors first, choose BFS. If you need to evaluate exhaustive paths, sort dependencies topologically, or verify connectivity across deep branches, DFS is the most intuitive and memory-efficient choice.