Graph Traversal
Visit every vertex — wide with BFS, deep with DFSA graph can have cycles and separate parts, so exploring it needs care. Breadth-first search visits the start, then everything one edge away, then two edges away — using a queue. Depth-first search follows one path as deep as it can and backtracks — using recursion. Pick a start vertex and watch each one work, with the adjacency list shown beside the graph.
- BFSa queue — nearest vertices first
- DFSrecursion — as deep as possible first
- Visited marksstop the search going round a cycle forever
- O(V + E)every vertex and edge handled once
- Current
- Waiting
- Visited
- Path
- 1distance (BFS) / visit order (DFS)
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Visit everything once
To explore a graph you need two helpers: a VISITED mark for every vertex (graphs can have cycles, so without marks the search would go round forever) and a place to remember which vertices are waiting. BFS keeps them in a QUEUE (nearest first); DFS keeps them on the call STACK (deepest first). Both read the neighbours of a vertex from an adjacency list.
int visited[V]; // 0 = not seen yet
// BFS: first in, first out
visited[s] = 1; enqueue(s);
while (!isEmpty()) {
int u = dequeue();
for (each neighbour v of u)
if (!visited[v]) { visited[v] = 1; enqueue(v); }
}
// DFS: go deep first (the call stack remembers the way back)
void dfs(int u) {
visited[u] = 1;
for (each neighbour v of u)
if (!visited[v]) dfs(v);
}
BFS (breadth-first)
- Mark the start as seen; put it in a QUEUE.
- Take the front vertex and visit it.
- Enqueue every neighbour not seen yet.
- Repeat until the queue is empty — level by level.
DFS (depth-first)
- Visit the vertex and mark it.
- For each neighbour not visited yet: DFS it now.
- Only when all neighbours are done, go back.
- Recursion (or a STACK) remembers the way back.
Mark vertices!
- Graphs can have cycles: A–B–C–A.
- Without a "visited" mark you would loop forever.
- Each vertex is visited once, each edge checked once (twice if undirected).
- So both searches are O(V + E).
Shortest path (unweighted)
- Run BFS from the start.
- Store dist[v] = dist[u] + 1 and parent[v] = u.
- BFS reaches every vertex by a shortest route first.
- Follow parent[] back from the target to read the path.
Where graphs are used
- Maps and navigation (road networks).
- Social networks: friends of friends.
- The web: pages linked to pages.
- Task planning: which job must come first.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
V = number of vertices, E = number of edges. With an adjacency list every search is O(V + E); with a matrix finding the neighbours of a vertex costs O(V), so the search becomes O(V²).
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| BFS (adjacency list) | O(V + E) |
O(V + E) |
O(V + E) |
Grows with n |
| DFS (adjacency list) | O(V + E) |
O(V + E) |
O(V + E) |
Grows with n |
| BFS / DFS (matrix) | O(V²) |
O(V²) |
O(V²) |
Grows with n |
| Is there an edge u–v? (matrix) | O(1) |
O(1) |
O(1) |
Instant |
| Is there an edge u–v? (list) | O(1) |
O(degree) |
O(V) |
Grows with n |
BFS vs DFS
| BFS | DFS | |
|---|---|---|
| Helper structure | Queue (FIFO) | Stack / recursion (LIFO) |
| Order | Level by level, nearest first | One branch as deep as possible |
| Shortest path (unweighted)? | Yes | No |
| Typical uses | Shortest routes, "friends of friends" | Cycle detection, mazes, topological sort |
| Time | O(V + E) | O(V + E) |
Check your understanding
Answer each question — you will see the explanation straight away.
Which data structure does BFS use to decide which vertex to visit next?
BFS visits vertices in the order they were discovered — first in, first out — so it uses a queue.
Why do BFS and DFS mark vertices as visited?
In A–B–C–A you could go round and round. The visited mark makes sure each vertex is handled only once.
An undirected graph has 5 edges. How many entries does its adjacency list have in total?
Each undirected edge u–v is stored twice: v in u's list and u in v's list.
Which search finds the path with the fewest edges in an unweighted graph?
BFS reaches all vertices at distance 1 before any at distance 2, so the first time it reaches a vertex it is along a shortest path.
A graph has 1,000 vertices and only 2,000 edges. Which representation uses less memory?
The matrix always needs 1,000 × 1,000 = 1,000,000 cells. The list needs about V + 2E = 5,000 entries.
What is the time complexity of BFS or DFS with an adjacency list?
Every vertex is visited once (V) and every edge is looked at once or twice (E).
Graphs quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.