1. What Is BFS (Breadth-First Search)?

Breadth-First Search (BFS) is a graph traversal algorithm that visits all vertices at the current depth level before moving to vertices at the next depth level. Think of it as exploring a graph in concentric rings outward from the source vertex.

BFS was first formalized by Konrad Zuse in 1945 and later independently described by Edward Moore (1959) for finding shortest paths through mazes. Today it underlies GPS shortest-route computation, social network friend suggestions, and peer-to-peer broadcasting.

2. What Is DFS (Depth-First Search)?

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It dives deep into one path until it hits a dead end (no unvisited neighbours), then retreats to the last branch point and tries another path.

DFS mimics how you solve a maze: walk straight until stuck, backtrack, try another corridor. It is the backbone of topological sorting, Tarjan’s SCC algorithm, and the recursive structure of many divide-and-conquer problems.

3. BFS Algorithm — Step-by-Step

Pseudocode

BFS(Graph G, source s):
  visited = set()
  queue  = empty Queue
  result = []

  visited.add(s)
  queue.enqueue(s)

  while queue is not empty:
    u = queue.dequeue()
    result.append(u)
    for each neighbour v of u in G:
      if v not in visited:
        visited.add(v)
        queue.enqueue(v)

  return result

Trace on a Sample Graph

Consider the undirected graph:

    1
   / \
  2   3
 / \   \
4   5   6

Starting BFS from vertex 1 (adjacency order: left before right):

BFS order: 1 → 2 → 3 → 4 → 5 → 6 (level by level)

BFS in Python

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue   = deque([start])
    order   = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order

4. DFS Algorithm — Step-by-Step

Pseudocode (Iterative)

DFS(Graph G, source s):
  visited = set()
  stack   = empty Stack
  result  = []

  stack.push(s)

  while stack is not empty:
    u = stack.pop()
    if u not in visited:
      visited.add(u)
      result.append(u)
      for each neighbour v of u in G (reverse order for left-to-right):
        if v not in visited:
          stack.push(v)

  return result

Trace on the Same Graph

DFS from vertex 1 (push neighbours in reverse so left child is processed first):

DFS order: 1 → 2 → 4 → 5 → 3 → 6 (deep into left branch first)

DFS in Python (Recursive)

def dfs(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for nb in graph[node]:
        if nb not in visited:
            dfs(graph, nb, visited, order)
    return order

5. BFS vs DFS: Full Comparison Table

6. Time and Space Complexity Analysis

Time Complexity: O(V + E) for Both

Each vertex is enqueued/pushed exactly once: O(V). Each edge is examined exactly twice (once from each endpoint in undirected graphs): O(E). Total: O(V + E).

Space Complexity: Where They Differ

Rule of thumb for GATE: BFS is better when the graph is deep but narrow; DFS is better when the graph is wide but shallow.

7. When to Use BFS vs DFS

8. GATE-Level Worked Examples

Example 1 — BFS Traversal Order (GATE 2019 pattern)

Vertices: {0,1,2,3,4,5}
Edges: 0-1, 0-2, 1-3, 1-4, 2-5
Adjacency list (sorted): 0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]

Queue: [0] → dequeue 0, enqueue 1,2 → Queue:[1,2]
Queue: [1,2] → dequeue 1, enqueue 3,4 → Queue:[2,3,4]
Queue: [2,3,4] → dequeue 2, enqueue 5 → Queue:[3,4,5]
dequeue 3 → no new → Queue:[4,5]
dequeue 4 → no new → Queue:[5]
dequeue 5 → no new → Queue:[]

Example 2 — DFS Back Edges (GATE 2022 pattern)

Edges: A→B, A→C, B→D, D→A, C→D

DFS path: A(1) → B(2) → D(3) → A [already visited, D→A is a back edge!]
         backtrack → C(4) → D [already visited, C→D is a cross edge]

Example 3 — Minimum Hops (BFS Shortest Path)

A - B - C - F
|
D - E - F  (another path)

Level 0: {A}
Level 1: {B, D}
Level 2: {C, E}
Level 3: {F} ← reached!

9. Five Common Mistakes Students Make

Mistake 1 — Marking visited AFTER dequeue in BFS

Many students mark a node visited when they dequeue it, not when they enqueue it. This causes the same node to be enqueued multiple times, leading to incorrect order and O(V²) or worse performance. Always mark visited when you enqueue, not when you dequeue.

Mistake 2 — Assuming DFS always finds the shortest path

DFS finds a path, not the shortest path. In an unweighted graph, only BFS guarantees that the first time you reach a node, you’ve taken the fewest edges. Exam questions frequently test this distinction.

Mistake 3 — Confusing back edges with cross edges in DFS

A back edge goes from a node to its ancestor (still on the DFS stack). A cross edge goes to a node in a different DFS subtree (already fully processed). Only back edges indicate cycles in directed graphs. Cross edges do not.

Mistake 4 — Ignoring disconnected components

A single BFS or DFS call from one source only visits the connected component containing that source. To traverse the entire graph, you must restart BFS/DFS from every unvisited vertex. Omitting this is a common source of wrong answers in GATE.

Mistake 5 — Stack overflow in recursive DFS on large graphs

Python has a default recursion limit of 1000. For a path graph of 10,000 nodes, recursive DFS crashes. The fix is either iterative DFS (explicit stack) or increasing the limit with sys.setrecursionlimit(). In GATE theory this doesn’t matter; in coding interviews it does.

10. Frequently Asked Questions

11. Next Steps