BFS vs. DFS: Which Graph Traversal Should You Use?

By Hourly DSA · September 25, 2026 · 4 min read

BFS explores a graph in layers; DFS follows a branch before coming back. Use BFS when you need the fewest edges from a starting point in an unweighted graph. Use DFS when following paths, exploring components, or organizing recursive work fits the question.

Both can visit every reachable vertex. The difference is the order of exploration and what that order tells you.

See the difference on a tiny graph

Consider these undirected connections:

A — B
A — C
B — D
D — E
C — E

Starting at A, breadth-first search visits A, then its neighbors B and C, then the remaining vertices D and E. Assuming B is processed before C, one valid BFS order is A, B, C, D, E.

Depth-first search might follow A, B, D, E, C, depending on neighbor order. It continues down the available branch before returning.

There isn't one universal DFS ordering. The graph and the order in which you examine neighbors determine the traversal.

Why BFS finds the fewest edges

From A, E can be reached along A → C → E in two edges. The path A → B → D → E takes three.

BFS reaches all vertices one edge away before exploring vertices two edges away. It reaches all vertices two edges away before exploring vertices three edges away. The first discovery of E therefore gives a minimum-edge path.

A DFS that follows B first can encounter E along the longer route. That first encounter doesn't prove a shortest path.

This BFS guarantee applies when every edge has equal cost, including an unweighted graph where the cost is simply one step. If edges carry different costs, the route with the fewest edges may be more expensive. You'll need an algorithm suited to those weights rather than ordinary BFS.

The queue is doing important work

A queue processes the earliest waiting vertex first. That preserves BFS's layer order.

A compact BFS looks like this:

queue = [start]
seen = {start}
while queue is not empty:
    vertex = remove_front(queue)
    for each neighbor of vertex:
        if neighbor is not in seen:
            add neighbor to seen
            add_back(queue, neighbor)

Use a queue implementation with efficient front removal. Repeatedly removing the first element of an array by shifting every other element can add avoidable work.

For path reconstruction, also record the parent of each vertex when you first discover it. Follow those parent links backward from the destination and reverse the result.

Why mark vertices when you add them?

Two different vertices might both lead to the same neighbor. Marking that neighbor as seen when you enqueue it prevents multiple pending copies.

This matters in cyclic graphs too. Without a seen set or equivalent state, A can lead to B, B can lead back to A, and the traversal may continue indefinitely.

A tree can sometimes avoid a full seen set by tracking the parent because it has no cycles. Don't carry that shortcut into an arbitrary graph without checking the assumptions.

When DFS is a natural fit

DFS works well when a question asks you to explore a connected region or finish work on descendants before returning to their parent. You can implement it recursively or with an explicit stack.

For example, to count connected components in an undirected graph, start a traversal from each vertex not already seen. Each new traversal identifies one component. Either BFS or DFS works; shortest-path ordering isn't needed.

Recursive DFS needs room for active calls. A long chain can create a call stack as deep as the number of vertices. An explicit stack can avoid a language's recursion-depth limit, though it still uses memory.

Time and space complexity

With adjacency lists, a full traversal is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is processed once, and each adjacency entry is inspected a bounded number of times.

Both algorithms can use O(V) extra space in the worst case for traversal state. BFS may hold a wide frontier. DFS may hold a deep path. “DFS always uses less memory” is not a reliable rule.

A quick choice to practice

You need the smallest number of moves through a grid. Every legal move costs one, and some cells are blocked. Which traversal should you investigate first?

BFS. Treat cells as vertices and legal moves as edges. Its layers correspond to move counts.

For more short decisions like this, practice with Hourly DSA. When reviewing an error, record the condition behind the choice: “equal-cost moves,” rather than just “grid means BFS.” Our mistake-review guide shows how to turn that distinction into a useful follow-up question.