Depth First Search (DFS) and Breadth First Search (BFS) are two fundamental graph traversal algorithms used in many areas of computer science, such as artificial intelligence, networks, and pathfinding. While both explore nodes in a graph or tree, they do so using different strategies and data structures.
2. Definition and Strategy
| Parameter | DFS (Depth First Search) | BFS (Breadth First Search) |
| Approach | Depth-first: explores as far as possible along each branch before backtracking. | Breadth-first: explores all neighbors at current depth before moving deeper. |
| Data Structure Used | Stack (can use recursion) | Queue |
| Traversal Order | Child nodes before siblings | Siblings before child nodes |
3. Algorithm (High-Level Steps)
DFS Algorithm:
1. Start at the source node.
2. Mark it as visited.
3. Recursively visit each unvisited neighbor.
4. Backtrack if no unvisited neighbors are left.
BFS Algorithm:
1. Start at the source node.
2. Enqueue the source node and mark it as visited.
3. Dequeue a node, visit it, and enqueue its unvisited neighbors.
4. Repeat until the queue is empty.
4. Example
DFS Traversal (A -> B -> C -> E -> D)
BFS Traversal (A -> B -> C -> D -> E)
5. Time and Space Complexity
| Operation | DFS | BFS |
| Time Complexity | O(V + E) | O(V + E) |
| Space Complexity | O(V) in worst case (due to recursion/stack) | O(V) due to queue |
V = number of vertices, E = number of edges
6. Key Differences
| Point | Depth First Search (DFS) | Breadth First Search (BFS) |
| 1. Strategy | Goes deep into each branch before backtracking. | Explores all neighbors at the current level before going deeper. |
| 2. Data Structure Used | Stack (can also use recursion). | Queue. |
| 3. Path Finding | Does not always give the shortest path. | Always gives the shortest path in an unweighted graph. |
| 4. Space Complexity | O(h) where h = height of the graph/tree. | O(w) where w = width of the graph/tree. |
| 5. Use Cases | Solving puzzles, topological sorting, cycle detection. | Finding shortest paths, level-order traversal, web crawling. |
| 6. Traversal Pattern | Depth-wise traversal (child before sibling). | Level-wise traversal (sibling before child). |
| 7. Implementation | Easier to implement with recursion. | Requires queue management (non-recursive). |
7. Applications
DFS:
• Solving mazes and puzzles (like Sudoku)
• Topological sorting
• Detecting cycles in graphs
• Strongly Connected Components (SCC)
BFS:
• Finding shortest path in unweighted graphs
• Web crawling
• Social networking (finding degrees of connection)
• Peer-to-peer networks