Difference Between BFS and DFS

Breadth-First Search (BFS) and Depth-First Search (DFS) are fundamental graph traversal algorithms. They differ in how they explore nodes and are used in various applications like searching and pathfinding.

What is BFS (Breadth-First Search)?

BFS explores nodes level by level. It visits all neighbors of a node before moving to the next level. It uses a queue data structure.

// BFS example (simplified)
#include <stdio.h>
#include <stdbool.h>

void bfs(int graph[5][5], int start) {
    bool visited[5] = {false};
    int queue[5], front = 0, rear = 0;

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

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

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

What is DFS (Depth-First Search)?

DFS explores as far as possible along a branch before backtracking. It uses a stack or recursion.

// DFS example (recursive)
#include <stdio.h>
#include <stdbool.h>

void dfs(int graph[5][5], int visited[], int node) {
    visited[node] = 1;
    printf("%d ", node);

    for (int i = 0; i < 5; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

Key Differences Between BFS and DFS

• BFS explores level by level, DFS explores depth-wise
• BFS uses queue, DFS uses stack/recursion
• BFS finds shortest path in unweighted graph, DFS does not guarantee
• BFS requires more memory, DFS uses less memory
• Traversal order differs significantly

Comparison Table

Example Scenario

BFS: Finding shortest path in maze
DFS: Solving puzzles like Sudoku

When to Use BFS?

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

When to Use DFS?

• Pathfinding with backtracking
• Cycle detection
• Topological sorting
• Solving puzzles

Real-World Applications

• BFS in GPS navigation
• DFS in maze solving
• BFS in social networks
• DFS in AI search problems
• Both in graph algorithms

Common Mistakes to Avoid

• Not marking visited nodes
• Using wrong data structure
• Infinite loops in graphs
• Incorrect recursion handling
• Ignoring memory constraints

Advanced Concepts

• Bidirectional BFS
• Iterative DFS
• Graph representations
• Connected components
• Cycle detection algorithms

Practice Exercises

• Implement BFS and DFS
• Find shortest path using BFS
• Detect cycles using DFS
• Traverse tree structures
• Compare performance

Conclusion

BFS and DFS are essential graph traversal techniques. BFS is ideal for shortest paths, while DFS is useful for deep exploration and backtracking problems.