1
BFS settles by distance
Every vertex at distance k is visited before any at distance k+1, which is exactly why its tree gives shortest paths.
Lesson · Graphs and Trees · Traversal
Breadth-First and Depth-First Search
Breadth-first search settles vertices in order of distance and therefore finds shortest paths in an unweighted graph. Depth-first goes as deep as possible first and is what detects cycles and orders dependencies.
BFS queue visits by increasing distance ⟹ shortest paths (unweighted)
DFS stack follows one branch to the end ⟹ cycles, components, ordering
both cost Θ(n + |E|) with adjacency lists
each produces a SPANNING TREE of its component
Queue or stack
Core ideas
What this lesson establishes
The two searches differ in one data structure and produce completely different trees.
2
DFS follows one branch to exhaustion
Then backtracks. Its tree is deep and narrow, and the order of backtracking is what topological sorting uses.
3
Both visit every vertex of the component
They differ in order, not in coverage. Both cost Θ(n + |E|) with adjacency lists.
The material
The two searches
Both algorithms, what each guarantees, and where each is used.
BFS(G, s):
mark s visited; dist[s] = 0; queue = [s]
while queue not empty:
v = queue.pop_front()
for each neighbour u of v:
if u unvisited:
mark u; dist[u] = dist[v] + 1; parent[u] = v
queue.push_back(u)
Theorem · BFS finds shortest paths
In an unweighted graph, dist[v] after BFS from s is the minimum number of edges on any s–v path.
By induction on the distance. Vertices at distance 0 and 1 are handled correctly by initialisation and the first round.
Suppose every vertex at true distance ≤ k is dequeued with the correct dist. A vertex v at true distance k+1 has a neighbour u at distance k; when u is processed, v is either already marked with a value at most k+1, or is marked k+1 then. It cannot be marked less, since that would give a shorter path.
The queue therefore holds vertices in non-decreasing distance order throughout.
□
The queue is doing the work. Replacing it with a stack gives depth-first search, and the distance guarantee vanishes immediately — DFS may reach a neighbour of the start by a long detour and record that depth.
DFS(G, v):
mark v visited
for each neighbour u of v:
if u unvisited: parent[u] = v; DFS(G, u)
What each is used for
BFS DFS
shortest paths (unweighted) cycle detection
level structure / distances topological sort
bipartiteness testing strongly connected components
web crawling by depth maze generation and solving
articulation points and bridges
Both find the components and both produce a spanning tree, and either serves for those. The distinctive uses come from the ORDER: BFS knows distances, DFS knows the nesting of the recursion, and each of those is the key to different problems.
Cycle detection with DFS
Theorem · Back edges are cycles
During a depth-first search of an undirected graph, an edge to an already-visited vertex that is not the current vertex's parent closes a cycle. A graph is acyclic exactly when no such edge is found.
This is what makes DFS the tool for cycle detection: the search tree plus a single back edge exhibits the cycle explicitly. The parent exclusion matters — without it every edge would look like a cycle of length 2.
Cost
Each vertex is marked once and each edge examined twice (once from each end), so both searches cost Θ(n + |E|) with adjacency lists and Θ(n²) with a matrix. For a sparse graph that is the difference between linear and quadratic, which is “Graph Representations”'s trade-off arriving in practice.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Running a search
Choose the structure from the question.
1
Pick BFS for distances
Shortest paths, level structure, bipartiteness. Anything where "how far" matters.
2
Pick DFS for structure
Cycles, dependency order, articulation points. Anything where the nesting of the search matters.
3
Mark on discovery, not on processing
Marking a vertex when it is added to the queue prevents it being added twice. Marking on removal is the classic bug.
4
Repeat from unvisited vertices
One search covers one component. A full traversal loops over starting points.
Traversal
Score 0 / 0Choose the answer you can justify.
Both searches on one graph
Vertices 1–6; edges 1–2, 1–3, 2–4, 3–4, 4–5, 5–6.
BFS from 1 (queue):
visit 1 dist 0
visit 2, 3 dist 1
visit 4 dist 2 (reached from 2)
visit 5 dist 3
visit 6 dist 4
order: 1 2 3 4 5 6 tree edges: 1–2, 1–3, 2–4, 4–5, 5–6
DFS from 1 (stack / recursion):
1 → 2 → 4 → 3 (3 is a dead end, backtrack)
4 → 5 → 6
order: 1 2 4 3 5 6 tree edges: 1–2, 2–4, 4–3, 4–5, 5–6
Different trees, same six vertices. Note DFS reached 3 at depth 3,
although its true distance from 1 is 1.
That last line is the reason DFS cannot be used for shortest paths. It found vertex 3 by the route 1→2→4→3, and the depth it records is a fact about the search order rather than about the graph. The edge 3–1 is a back edge — at vertex 3 the neighbour 1 is already visited and is not 3's parent — and it closes the cycle 1–2–4–3–1. 4–3 is a tree edge, since 3 was discovered from 4.
Common mistakes
1
Using DFS for shortest pathsThe depth it records is an artefact of the search order. Only BFS guarantees distance.
2
Marking vertices on removal rather than on discoveryA vertex can then be queued several times before it is processed, which breaks both the cost bound and the distance guarantee.
3
Forgetting to exclude the parent in cycle detectionOtherwise every edge looks like a cycle back to where you came from.
Check your understanding
✓
Finish when you can predict both visit orders on a small graph.
Take a graph on seven vertices, write out the BFS and DFS orders by hand, and mark the tree edges of each. The two trees should look nothing alike.
Note: Dijkstra's algorithm in “Shortest Paths and Dijkstra's Algorithm” is BFS with a priority queue in place of the queue. The correspondence is exact, and it is why Dijkstra reduces to BFS when every weight is 1.