Difference Between BFS and DFS with Example

1. Introduction

Breadth-First Search (BFS):

BFS is a graph traversal algorithm that starts at the source node and explores all its neighboring nodes level by level, moving outward before going deeper.

Depth-First Search (DFS):

DFS explores a graph by going as deep as possible down one path before backtracking. It uses recursion or a stack.

2. BFS vs DFS – Key Differences Table

3. BFS and DFS with Example

Consider the graph below:

     A
   /   \
  B     C
  |     |
  D     E

Adjacency List Representation

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

4. BFS Implementation (Python)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

bfs(graph, 'A')

BFS Output:

A B C D E

5. DFS Implementation (Recursive)

visited = set()

def dfs(graph, node):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor)

dfs(graph, 'A')

DFS Output:

A B D C E

Note: DFS output may vary depending on neighbor order in the list.

6. Visualization of Traversal

BFS (Level Order)

• Visit A
• Then its neighbors B, C
• Then their children D, E

Traversal order:
A → B → C → D → E

DFS (Depth First)

• Visit A
• Go deep to B, then to D
• Backtrack to A, then go to C, then E

Traversal order:
A → B → D → C → E

7. Applications of BFS

• Shortest path in unweighted graphs
• Peer-to-peer networks (e.g., BitTorrent)
• Web crawlers
• Social networking websites (finding people within k connections)
• GPS Navigation (unweighted roads)

8. Applications of DFS

• Cycle detection
• Solving puzzles (e.g., Sudoku, Maze)
• Topological sorting
• Strongly connected components (Kosaraju’s algorithm)
• Checking bipartite graphs
• Connected components in undirected graphs

9. Time and Space Complexity

10. Summary: When to Use BFS vs DFS