Important: Both BFS and DFS assume you have an adjacency list (or matrix) that tells you the neighbors of any node instantly.
Breadth-first search (BFS) is a core graph traversal method that explores a network from a source node, usually to find a desired attribute (often the shortest path to every other node).BFS explores all nodes at the current “level” (breadth) of the tree before going any deeper. It spreads outward like a ripple rather than diving down like DFS.
Complexity
Time complexity: The algorithm visits every node and every edge just once, so the total amount of work is proportional to the number of nodes (\(V\)) plus the number of edges (\(E\)) in the graph. This is written as \(O(V + E)\), it’s efficient even on large graphs.
Space (memory)complexity: Breadth-first search keeps track of which nodes it needs to explore next (the queue) and which nodes it has already visited (the visited set). Both of these will use up to \(O(V)\) memory (RAM), meaning the amount of memory required is proportional to the number of nodes.
Source: DOI:10.1017/97811086539471
BFS(graph, start):
queue ← [start]
visited ← {start}
while queue is not empty:
node ← dequeue(queue)
process(node)
for each neighbor of node:
if neighbor not in visited:
visited.add(neighbor)
enqueue(queue, neighbor)
Consider the following undirected graph:
A
/ \
B C
/ \ \
D E F
A.A, mark as visited.A, process it.B and C, mark them as visited.B, process it.D and E, mark them as visited.C, process it.F, mark it as visited.queue to keep track of the process (For more details see: https://www.youtube.com/watch?v=oDqjPvD54Ss )BFS naturally builds a tree by recording, for each node, which node discovered it (its “parent”), and because BFS processes nodes level by level, that parent relationship guarantees the path traced back from any node to the root through those parent pointers is the shortest possible path.
shortest-path tree
Unlike Breadth-First Search (BFS), which explores all neighbors at the current depth before moving to the next layer, Depth-First Search (DFS) explores as far as possible along each branch before backtracking.
Given a graph \(G = (V, E)\) and a starting node \(s\), DFS systematically visits every reachable node by always advancing to an unvisited neighbor before retreating.
The key data structure is a stack (either explicit, or implicitly via recursion).
A stack is a list where you can only add and remove from the top, the last item you put in is the first one you take out (LIFO). In DFS, this means you always explore the most recently discovered neighbor next, which is what drives the algorithm deep before it goes wide.
pop removes and returns the top item from the stack, so after a pop, that item is gone from the stack and you’re “holding it” to work with.
DFS(graph, start):
stack ← [start]
visited ← {}
while stack is not empty:
node ← pop(stack)
if node not in visited:
visited.add(node)
process(node)
for each neighbor of node:
if neighbor not in visited:
push(stack, neighbor)
The one thing that makes it DFS specifically is the stack (last-in, first-out), swapping it for a queue turns this into BFS.
Consider this undirected graph:
A
/ \
B C
/ \ \
D E F
Represented as an adjacency list:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}Starting DFS at A, one possible traversal order is:
| Step | Node Visited | Stack (after step) |
|---|---|---|
| 1 | A | [B, C] |
| 2 | B | [D, E, C] |
| 3 | D | [E, C] |
| 4 | E | [C] |
| 5 | C | [F] |
| 6 | F | [] |
Visit order: A → B → D → E → C → F
When DFS runs on a graph, it naturally produces a DFS tree. Edges in the original graph fall into one of four categories:
| Edge Type | Description |
|---|---|
| Tree edge | Edge used to discover a new node |
| Back edge | Edge to an ancestor in the DFS tree (indicates a cycle) |
| Forward edge | Edge to a descendant (directed graphs only) |
| Cross edge | Edge between nodes in different DFS subtrees (directed graphs only) |
| Complexity | |
|---|---|
| Time | \(O(V + E)\), every node and edge is visited once |
| Space | \(O(V)\), for the visited set and recursion stack |
For dense graphs where \(E \approx V^2\), this simplifies to \(O(V^2)\).
Cycle detection: a back edge in the DFS tree means the graph has a cycle.
Topological sort: for a directed acyclic graph (DAG), output nodes in reverse order of their finish times.
Connected components: run DFS from each unvisited node; each separate DFS call finds one component.
Strongly connected components (SCCs): Kosaraju’s and Tarjan’s algorithms both build on DFS.
Solving mazes and puzzles: DFS naturally models exhaustive search with backtracking.
| DFS | BFS | |
|---|---|---|
| Data structure | Stack | Queue |
| Explores | Deep first | Wide first |
| Shortest path? | No (unweighted) | Yes (unweighted) |
| Memory usage | \(O(depth)\) | \(O(width)\) |
| Good for | Cycle detection, topological sort, SCCs | Shortest paths, level-order traversal |