juniorGraph Theory

What is the difference between BFS and DFS graph traversal?

Updated Feb 20, 2026

Short answer

BFS explores a graph level by level using a queue, visiting all neighbours at distance 1 before any at distance 2. DFS follows one path as deep as possible before backtracking, using a stack or recursion. Both visit every reachable vertex in O(V+E), but BFS finds the shortest path in an unweighted graph while DFS does not — and their memory profiles differ sharply depending on the graph's shape.

Deep explanation

The algorithms are structurally identical apart from the container holding pending vertices — a queue for BFS, a stack for DFS. That single swap changes the traversal order and everything that follows from it.

Python
from collections import deque


def bfs(graph, start):
    visited, order = {start}, []
    queue = deque([start])
    while queue:
        node = queue.popleft()        # FIFO -> level by level
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)      # mark on ENQUEUE, not on dequeue
                queue.append(nbr)
    return order


def dfs(graph, start, visited=None):
    visited = visited or set()
    visited.add(start)
    order = [start]
    for nbr in graph[start]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)
    return order

Shortest path. BFS dequeues vertices in non-decreasing distance from the source, so the first time it reaches a vertex it has done so by a minimum-edge-count path. DFS offers no such guarantee — it may reach a neighbour by a long detour. This holds only for unweighted graphs; with weights you need Dijkstra.

Memory. BFS holds an entire frontier, which for a wide graph with branching factor b at depth d is O(b^d). DFS holds only the current path, O(d) — or O(V) worst case for a path-shaped graph. On a wide, shallow graph DFS wins on memory; on a deep, narrow one BFS avoids stack overflow.

Where each is used. BFS: shortest hop count, level-order processing, bipartiteness checking, web crawling by depth. DFS: cycle detection, topological sort, strongly connected components, maze and backtracking problems.

One implementation detail causes most bugs: in BFS, mark a vertex visited when you enqueue it, not when you dequeue it. Otherwise a vertex reachable from several frontier nodes is enqueued multiple times, and the queue can blow up.

Real-world example

A social network computes degrees of separation between two users.

Python
def degrees_of_separation(graph, source, target):
    if source == target:
        return 0
    visited = {source}
    queue = deque([(source, 0)])
    while queue:
        person, depth = queue.popleft()
        for friend in graph[person]:
            if friend == target:
                return depth + 1          # first arrival == shortest
            if friend not in visited:
                visited.add(friend)
                queue.append((friend, depth + 1))
    return -1                              # unreachable

BFS is required here: the first time the target is reached, it is by the fewest hops. DFS might find the target through a chain of forty acquaintances while a mutual friend sat one hop away — it would return a path, not the shortest.

Conversely, detecting whether a build dependency graph contains a circular dependency is a DFS job: you track vertices on the current recursion stack and report a cycle when you encounter one again.

Common mistakes

  • - Marking vertices visited on dequeue rather than enqueue in BFS, allowing duplicates into the queue and inflating memory.
  • - Using DFS for shortest paths — it finds a path, not the shortest one.
  • - Assuming BFS gives shortest paths in a *weighted* graph
  • it counts edges, not weights, so Dijkstra is required.
  • - Recursive DFS on a deep graph, overflowing the call stack
  • an explicit stack avoids it.
  • - Omitting the visited set on a cyclic graph, producing an infinite loop.
  • - Not distinguishing 'currently on the recursion stack' from 'visited at some point' during DFS cycle detection — the two sets answer different questions.

Follow-up questions

  • How do you detect a cycle in an undirected graph with DFS?
  • Why can't BFS find shortest paths in weighted graphs?
  • What is bidirectional BFS and when does it help?
  • Which traversal underpins topological sorting?

More Graph Theory interview questions

View all →