Side by side

Breadth-First SearchvsDepth-First Search

What is the difference between BFS and DFS?

Updated September 30, 20262 min read7 differences

In short

BFS explores a graph level by level with a queue, finding shortest paths in unweighted graphs, while DFS goes deep down one branch, then backtracks.

Data Structuresp. 8

Breadth-First Search

Breadth-first search is a graph traversal algorithm that visits nodes in order of their distance from the start, exploring all neighbors before going deeper.

Read the page on Breadth-First Search

Data Structuresp. 10

Depth-First Search

Depth-first search is a graph traversal algorithm that follows one path as far as it can go before backtracking to explore the next unvisited branch.

Read the page on Depth-First Search

Breadth-First Search and Depth-First Search compared

Aspect	Breadth-First Search	Depth-First Search
Exploration order	Level by level, nearest nodes first	One branch as deep as possible, then backtrack
Data structure	A queue (FIFO)	A stack (LIFO) or recursion
Shortest path	Guaranteed in unweighted graphs	Not guaranteed
Memory use	Grows with the widest level of the graph	Grows with the depth of the current path
Time complexity	O(V + E)	O(V + E)
Very deep graphs	Never gets lost down one long branch	Deep recursion can overflow the call stack
Typical uses	Shortest paths, nearest matches, level-order traversal	Cycle detection, topological sort, puzzles and mazes

The difference, explained

Breadth-first search (BFS) and depth-first search (DFS) are the two basic ways to visit every node of a graph or tree. BFS visits all neighbors of the start node first, then their neighbors, spreading outward in rings. DFS picks one neighbor and keeps going deeper until it reaches a dead end, then backtracks to try the next option.

The difference comes from the data structure behind each one. BFS uses a queue, so nodes are processed in the order they were discovered, which guarantees it reaches every node by the fewest possible edges. DFS uses a stack, often the call stack through recursion, so it always continues from the most recently discovered node.

Both run in O(V + E) time, where V is the number of vertices (nodes) and E the number of edges, and both need a visited set to avoid looping forever in graphs with cycles. Many algorithms build on them: BFS powers shortest paths in unweighted graphs and friend-of-a-friend suggestions, while DFS powers cycle detection, topological sorting and maze solving.

A common misconception is that DFS finds the shortest path. It finds a path, but not necessarily the shortest one; and when edges have weights, such as road distances, neither is enough on its own, so algorithms like Dijkstra's are used instead.

Which one should you use?

Choose Breadth-First Search when…

You need the shortest path in an unweighted graph.
The target is likely close to the starting node.
You want to process nodes level by level.

Choose Depth-First Search when…

You need to explore every possible path, as in puzzles or backtracking.
You are detecting cycles or ordering dependencies.
The graph is very wide and a full level would not fit in memory.

Visiting every node of a graph

Breadth-First Searchpython

from collections import deque

def bfs(graph, start):
    visited, queue = {start}, deque([start])
    while queue:
        node = queue.popleft()      # oldest node first
        print(node)
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                queue.append(n)

Depth-First Searchpython

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for n in graph[node]:
        if n not in visited:
            dfs(graph, n, visited)  # go deeper first
    return visited

Readers ask

Is BFS or DFS faster?

Both visit each node and edge once, so both take O(V + E) time. Which one finds a target sooner depends on where it is: BFS for nearby targets, DFS for deep ones.

Which uses more memory, BFS or DFS?

BFS usually does on wide graphs, because its queue can hold an entire level at once. DFS stores only the current path, although a very deep graph can make that path long.

Do BFS and DFS work on trees?

Yes. On a tree, BFS is also called level-order traversal, while DFS covers the preorder, inorder and postorder traversals.