BFS (breadth-first search) visits a graph level by level, nearest vertices first, keeping the vertices waiting their turn in a queue. DFS (depth-first search) follows one path as deep as it goes, then backtracks, keeping that path on a stack. Both take O(V + E) time with an adjacency list. Use BFS for shortest paths by edges, DFS for backtracking.
Below, both run step by step on the same tree, so you can compare them move by move.
// bfs vs dfs
Both players start from A on one tree, the BFS topic's default graph, each in its own scene from the app: BFS with its queue, DFS with its stack, the adjacency matrix beside both. BFS visits A, B, E, C, F, D, a level at a time; DFS visits A, B, C, D, E, F, finishing the branch through B before it turns to E. The dotted line joins each vertex to the next one visited. In DFS it follows the edges except from D to E, where DFS has backtracked; in BFS it leaves the edges after A to B.
On the same tree, the stack holds the path from A down to the vertex DFS stands on.
Breadth-first search and depth-first search both visit every vertex they can reach from a start vertex, each exactly once. They differ in the order, and the order comes from the container that holds the vertices still to explore.
| BFS | DFS | |
|---|---|---|
| Order | Level by level, nearest first | One path to its end, then back |
| Container | Queue: first in, first out | Stack or recursion: last in, first out |
| On the tree above | A, B, E, C, F, D | A, B, C, D, E, F |
| Time | The same: O(V + E) with an adjacency list, O(V2) with an adjacency matrix | |
| Extra space | O(V): the queue, up to two levels | O(V): the stack, one path |
| Fewest edges to each vertex | Yes, in an unweighted graph | Not guaranteed |
| Recursive version | None natural | Yes, on the call stack |
| Strength | Finds what lies near the start first | Holds only the current path |
| Weak spot | A wide graph fills the queue | A long path fills the stack |
| Typical uses | Shortest paths by edges, levels, bipartite check | Backtracking, cycles, topological order |
Both searches find neighbors the same way: findUnvisitedNeighbor(u) scans row u of the adjacency matrix from the left and returns the first unvisited vertex with a 1 in its column. What differs is which vertex they ask next. BFS dequeues the vertex that has waited longest and visits all its unvisited neighbors before it takes the next one, so the search spreads one level at a time. DFS peeks at the vertex pushed last, visits one neighbor and goes on from there at once, so it runs down a path until a dead end, then pops back to the nearest vertex with a neighbor left. In pseudocode, with the app's names for visit and findUnvisitedNeighbor:
bfs(start)
queue = empty queue
visit(start)
queue.enqueue(start)
while queue is not empty
u = queue.dequeue()
v = findUnvisitedNeighbor(u)
while v is not none
visit(v)
queue.enqueue(v)
v = findUnvisitedNeighbor(u)
dfs(start)
stack = empty stack
visit(start)
stack.push(start)
while stack is not empty
u = stack.peek()
v = findUnvisitedNeighbor(u)
if v is none
stack.pop()
else
visit(v)
stack.push(v)
findUnvisitedNeighbor(u)
for v from 0 to V - 1
if matrix[u][v] == 1
if v is not visited
return v
return none
Vertices are numbered from 0, and visit marks a vertex as visited. Give DFS's loop a queue in place of the stack, reading the front vertex and dequeuing it when it has no unvisited neighbor left, and it visits in BFS order.
In an unweighted graph BFS reaches every vertex by a path with the fewest edges, as it finishes each level before it starts the next. DFS reaches a vertex by whatever path it happens to be on. On a triangle of A, B and C, DFS from A goes to B first and reaches C through B, two edges, while BFS finds C one edge from A. On the players' tree each vertex has a single path from A, so both find the same ones.
With weights neither is enough, as both count edges. Dijkstra's algorithm finds the lowest total weight when no weight is negative, and Bellman-Ford handles negative weights too.
The time is the same. Each vertex is visited once, and the work goes into finding neighbors: O(V + E) with an adjacency list, which holds only real neighbors, and O(V2) with an adjacency matrix, whose rows have V cells each.
Both need O(V) extra space at worst, but they fill it on different graphs. The BFS queue holds at most two neighboring levels, so a wide graph fills it: on a star, one center joined to every other vertex, BFS from the center enqueues all the others at once, while the DFS stack never holds more than two. The DFS stack holds the path from the start, so a long path fills it: on a chain of V vertices, from one end, DFS pushes all of them, while the BFS queue holds one at a time. On the players' tree the queue holds at most two vertices and the stack four.
A recursive DFS keeps that path on the call stack, one nested call per vertex, so on deep graphs an explicit stack is the safe choice.
Note
Python's default recursion limit stops a recursive DFS at about 1,000 nested calls with RecursionError.
Use BFS when the answer lies near the start or must take the fewest steps:
Use DFS when you follow whole paths or need the graph's structure:
For reachability and connected components either works: both visit exactly the vertices that some path joins to the start, in O(V + E).
The queue hands out vertices in the order they were found: every vertex one edge from the start before any two edges away, and so on. The first path by which BFS reaches a vertex is therefore one with the fewest edges. DFS takes whichever path it is on when it first meets a vertex, however long.
Not naturally. Recursion keeps its calls on the call stack, last in, first out, which can stand in for the stack of DFS but not for a first-in, first-out queue.
O(V2) for both. Every scan of a row reads up to V cells, and with findUnvisitedNeighbor above a search that reaches every vertex makes 2V − 1 scans: 11 for the six vertices of the players' tree. With an adjacency list, both take O(V + E).
With DFS: an edge to a vertex that is still on the stack is a back edge and closes a cycle. With BFS: Kahn's algorithm removes vertices with no incoming edges; if some vertices are never removed, they lie on a cycle or can be reached from one.
BFS, as it reaches the nearest exit first, by the fewest moves. To learn only whether any exit can be reached, either search works.
// in the app
In VisiGrab, BFS and DFS each have a topic with four example graphs, and the Graph Constructor runs either one on a graph you draw.
In the Graph Constructor, place up to 12 vertices, drag edges between them and tap Apply. Flip the DFS / BFS switch and tap the start vertex: each tap on Next visits one vertex and adds it to the traversal order.
BFS runs on a tree, a ring of six vertices, a graph with two triangles and a fan; DFS on a tree of nine, a graph with a cycle, three chains hanging from A and a ring of eight. Each shows its queue or stack and the adjacency matrix.
The BFS info dialog defines it as closest vertices first, counted in edges. The DFS one has two tabs: graphs and their representations, then dead ends, backtracking and O(V + E) against O(V²).
BFS's loop over a queue and DFS's over a stack, with its recursive version, in all three languages, sharing findUnvisitedNeighbor. Each listing links to its full source on GitHub.
Four questions on BFS and ten on graphs and DFS, with an explanation for every answer.
Topological sort, Dijkstra, Bellman-Ford, Prim, Kruskal and union-find each have a topic of their own.
// build your own
Download VisiGrab to watch the queue and the stack at work on example graphs, then draw a graph of your own and run both searches on it.
BFS and DFS each have a topic among 30+. See them all