Google Maps finding a route, LinkedIn suggesting “people you may know”, a game AI escaping a maze: under the hood these are all graphs, and the two basic ways to explore them are BFS and DFS. “BFS vs DFS” is a top-five DSA interview topic, and it's much easier than it sounds once you watch both run on the same graph.
This guide covers what a graph is, how to store one, BFS and DFS with a step-by-step animation, a clear difference table, code in Python, Java and C++, and a memory trick you'll still have in the exam hall.
What is a graph in data structure?
A graph is the most general way to model connections: cities and roads, people and friendships, web pages and links. It has two parts:
- Vertices (nodes): the things, like cities or people.
- Edges: the connections between them.
Graphs come in a few flavours:
- Undirected (friendship goes both ways) vs directed (you follow someone who doesn't follow back).
- Unweighted vs weighted (each road has a distance or cost).
- Cyclic vs acyclic. A tree is a connected graph with no cycles.
How to store a graph: adjacency list vs matrix
- Adjacency list: for each vertex, a list of its neighbours (
A: [B, C]). Uses O(V + E) space. This is the default for most problems. - Adjacency matrix: a V × V grid of 0s and 1s. Uses O(V²) space but answers “is there an edge from u to v?” in O(1). Good for small, dense graphs.
BFS vs DFS: watch them run
Same graph, same start (A), same neighbour order. Switch between BFS and DFS and step through. Watch the visit order and the queue or stack on the right:
🎮 BFS vs DFS on the same graph
Queue (front → back)
Take from the front, add to the back (FIFO).
Visit order
A
Adjacency list
- A: B, C
- B: A, D, E
- C: A, F
- D: B
- E: B, F, G
- F: C, E
- G: E
Step 1 of 9. Start: mark A visited and put it in the QUEUE.
How BFS works (breadth-first search)
- Mark the start as visited and put it in a queue.
- Take the node at the front of the queue.
- Add each of its unvisited neighbours to the back, marking them visited.
- Repeat until the queue is empty.
Because the queue is first in, first out (the same queue from part 6), all nodes one step away are processed before any node two steps away.
How DFS works (depth-first search)
- Mark the current node visited.
- For each unvisited neighbour, immediately go there and repeat (go deep).
- When a node has no unvisited neighbours, backtrack to the previous node.
Written recursively, DFS is just a few lines: the call stack remembers the path back for you. Preorder, inorder and postorder tree traversals are all DFS.
🧠 PATH memory card
Remember BFS vs DFS for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
Drop a pebble in the village pond and the ripples spread one ring at a time: that's BFS. Walk into a maze, follow one corridor until a dead end, chalk the wall and step back: that's DFS.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Ripples go Broad (Queue), Mazes go Deep (Stack)”
- Ripples→BFS: spreads evenly, ring by ring
- Broad→B = Breadth: all neighbours before going further
- Queue→BFS uses a queue (FIFO)
- Mazes→DFS: follow one corridor to the end
- Deep→D = Depth: go as far as possible, then backtrack
- Stack→DFS uses a stack or recursion (LIFO)
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Graph: A–B, A–C, B–D, B–E, C–F, E–F, E–G. BFS from A: A, then its ring B C, then the next ring D E F, then G → A B C D E F G. DFS from A: A → B → D (dead end, back) → E → F → C (back up) → G → A B D E F C G. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 9 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
BFS vs DFS: difference table
| Feature | BFS | DFS |
|---|---|---|
| Full name | Breadth-First Search | Depth-First Search |
| Strategy | Level by level, nearest first | One path as deep as possible, then backtrack |
| Data structure | Queue (FIFO) | Stack (LIFO) or recursion |
| Shortest path (unweighted)? | Yes, guaranteed | No |
| Memory | O(V): can hold a whole level | O(V) worst case, often just the current path's depth |
| Time | O(V + E) | O(V + E) |
| Typical uses | Shortest path, level order, nearby friends, web crawling | Backtracking, cycle detection, topological sort, mazes, connected components |
| Real-life picture | Ripples in a pond | Exploring a maze with chalk |
BFS and DFS code (Python, Java, C++)
The same graph as the animation, so you can check the output against what you just watched.
from collections import deque
graph = { # adjacency list (undirected)
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F", "G"],
"F": ["C", "E"],
"G": ["E"],
}
def bfs(start): # O(V + E)
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # take from the FRONT
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb) # mark when added, not when popped
queue.append(nb) # add to the BACK
return order
def dfs(node, visited=None): # O(V + E), recursive
if visited is None:
visited = []
visited.append(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb, visited) # go DEEP first
return visited
def shortest_path_length(start, goal): # BFS distances
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
if node == goal:
return dist[node]
for nb in graph[node]:
if nb not in dist:
dist[nb] = dist[node] + 1
queue.append(nb)
return -1
print(bfs("A")) # ['A', 'B', 'C', 'D', 'E', 'F', 'G']
print(dfs("A")) # ['A', 'B', 'D', 'E', 'F', 'C', 'G']
print(shortest_path_length("A", "G")) # 3 (A -> B -> E -> G)When to use BFS and when to use DFS
🧩 BFS or DFS?
6 real problemsShortest route by number of stops (unweighted map)
Solve a maze or a Sudoku by trying a path and backtracking
Find “friends of friends” within 2 connections
Detect a cycle or do a topological sort of course prerequisites
Level-order traversal of a tree
Find all connected components (islands) in a grid
For weighted graphs (roads with different lengths), plain BFS no longer gives the shortest path. That's where Dijkstra's algorithm comes in: BFS with a priority queue instead of a normal queue.
What to learn next
You can now explore any structure. The final part of the course teaches you to solve hard problems fast by remembering answers you've already computed: dynamic programming.
Key takeaways
- ✓A graph is vertices connected by edges: directed or undirected, weighted or not.
- ✓Store it as an adjacency list (usual) or an adjacency matrix (dense graphs).
- ✓BFS: level by level with a queue; finds shortest paths in unweighted graphs.
- ✓DFS: deep first with a stack or recursion; great for backtracking and cycles.
- ✓Both are O(V + E). Always keep a visited set.
- ✓Remember it with “Ripples go Broad (Queue), Mazes go Deep (Stack).”
Frequently asked questions
What is the difference between BFS and DFS?
BFS (breadth-first search) explores a graph level by level: all neighbours first, then their neighbours, using a queue. DFS (depth-first search) follows one path as deep as possible before backtracking, using a stack or recursion. BFS finds shortest paths in unweighted graphs; DFS is natural for backtracking, cycle detection and topological sorting.
Which data structure is used in BFS and DFS?
BFS uses a queue (first in, first out), so nodes discovered earlier are explored earlier. DFS uses a stack (last in, first out), either an explicit stack or the function call stack when written recursively.
What is the time complexity of BFS and DFS?
Both are O(V + E) with an adjacency list, where V is the number of vertices and E the number of edges, because each vertex is visited once and each edge is checked a constant number of times. With an adjacency matrix both become O(V²).
Why does BFS find the shortest path?
BFS visits nodes in order of their distance (number of edges) from the start: first everything at distance 1, then distance 2, and so on. So the first time it reaches a node is along a path with the fewest edges. This only holds for unweighted graphs; weighted graphs need Dijkstra's algorithm.
What is an adjacency list and an adjacency matrix?
Both store a graph's edges. An adjacency list keeps, for each vertex, a list of its neighbours: compact, O(V + E) space, best for sparse graphs. An adjacency matrix is a V × V grid where cell [u][v] says whether an edge exists: O(V²) space, but checking a specific edge is O(1).
🧠 Quick check: BFS vs DFS
1. Which traversal is guaranteed to find the shortest path (fewest edges) in an unweighted graph?
2. A recursive DFS function uses which data structure behind the scenes?
3. Why do BFS and DFS keep a visited set?
4. In “Ripples go Broad, Mazes go Deep”, which one uses a queue?
Checking your access…