Difference Between DFS and BFS

Depth-First Search (DFS) and Breadth-First Search (BFS) are two fundamental graph traversal algorithms. They are used to explore nodes and edges of a graph but differ in approach, data structures used, and performance characteristics.

What is DFS (Depth-First Search)?

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses a stack data structure (or recursion).

// DFS using recursion
#include <stdio.h>
#define V 4

int graph[V][V] = {
    {0,1,1,0},
    {1,0,0,1},
    {1,0,0,1},
    {0,1,1,0}
};

int visited[V] = {0};

void dfs(int node) {
    visited[node] = 1;
    printf("%d ", node);
    for(int i = 0; i < V; i++) {
        if(graph[node][i] && !visited[i]) {
            dfs(i);
        }
    }
}

What is BFS (Breadth-First Search)?

BFS explores a graph level by level, visiting all neighbors before moving to the next level. It uses a queue data structure.

// BFS using queue
#include <stdio.h>
#define V 4

int graph[V][V] = {
    {0,1,1,0},
    {1,0,0,1},
    {1,0,0,1},
    {0,1,1,0}
};

void bfs(int start) {
    int visited[V] = {0};
    int queue[V], front = 0, rear = 0;

    visited[start] = 1;
    queue[rear++] = start;

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

        for(int i = 0; i < V; i++) {
            if(graph[node][i] && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

Key Differences Between DFS and BFS

• DFS uses stack (or recursion), BFS uses queue
• DFS goes deep first, BFS goes level by level
• DFS may not find shortest path, BFS guarantees shortest path in unweighted graphs
• DFS uses less memory in sparse graphs, BFS may use more memory
• BFS is better for shortest path problems

Comparison Table

Traversal Example

// Call traversals
// dfs(0);
// bfs(0);

When to Use DFS?

• Backtracking problems
• Cycle detection
• Topological sorting
• Maze solving

When to Use BFS?

• Shortest path in unweighted graphs
• Level-order traversal
• Network broadcasting
• Finding minimum steps problems

Real-World Applications

• DFS in puzzle solving
• BFS in GPS navigation
• DFS in AI search
• BFS in social networks
• Both in graph processing systems

Common Mistakes to Avoid

• Not marking nodes as visited
• Using wrong data structure
• Infinite loops in cyclic graphs
• Ignoring graph representation
• Incorrect traversal logic

Advanced Concepts

• Iterative DFS
• Bidirectional BFS
• Weighted graphs
• A* algorithm
• Graph optimization techniques

Practice Exercises

• Implement DFS iteratively
• Find shortest path using BFS
• Detect cycle using DFS
• Traverse disconnected graph
• Compare DFS vs BFS performance

Conclusion

DFS and BFS are essential graph traversal techniques. DFS is useful for deep exploration and backtracking, while BFS is ideal for shortest path and level-wise traversal. Choosing the right algorithm depends on the problem.