Graph search: BFS, DFS and shortest paths
Breadth-first search (BFS) explores an unweighted graph by layers and finds shortest paths by edge count; depth-first search (DFS) follows a path deeply before backtracking.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
V vertices and E edges are counts; d is an integer edge count; runtime is measured in graph operations
Variables & units
| Symbol | Meaning | Unit |
|---|---|---|
| Finite graph with vertex set V and edge set E | nodes and edges | |
| Start vertex and reachable target vertex | nodes | |
| Minimum number of edges in a path from s to v | edges | |
| Number of elementary search operations using adjacency lists | operations |
LaTeX
d(s,v)=\min_{p:s\leadsto v}|p|\quad(\text{Einheitskanten}),\qquad T_{BFS},T_{DFS}=O(|V|+|E|)
Original schematic by Quanta
Free with a Quanta account. Your download stays ready after registration.
Derivation & background
BFS uses a FIFO queue and discovers vertices in nondecreasing distance from the start. It therefore finds shortest paths in unweighted graphs or graphs with equal edge costs; with unequal weights, use an algorithm such as Dijkstra instead. DFS typically uses a stack or recursion and is useful for reachability, connectivity and structure, but does not guarantee a shortest path. With adjacency lists, reachable vertices and edges are processed only a constant number of times, giving O(|V|+|E|); an adjacency matrix typically costs O(|V|2).
Exam blueprint
Validity range
BFS uses a FIFO queue and discovers vertices in nondecreasing distance from the start. It therefore finds shortest paths in unweighted graphs or graphs with equal edge costs; with unequal weights, use an algorithm such as Dijkstra instead. DFS typically uses a stack or recursion and is useful for reachability, connectivity and structure, but does not guarantee a shortest path. With adjacency lists, reachable vertices and edges are processed only a constant number of times, giving O(|V|+|E|); an adjacency matrix typically costs O(|V|2).
Derivation steps
Breadth-first search (BFS) explores an unweighted graph by layers and finds shortest paths by edge count; depth-first search (DFS) follows a path deeply before backtracking.
- 1Read the relation from its definition: d(s,v)=\min_{p:s\leadsto v}|p|\quad(\text{Einheitskanten}),\qquad TBFS,TDFS=O(|V|+|E|).
- 2Identify the input, requested output and assumptions of the relation.
- 3Consider edges s–a, s–b, a–t, b–c and c–t. BFS finds d(s,t)=2 via s–a–t. If DFS explores b before a, it may first discover t via s–b–c–t, a three-edge route. Both searches take O(|V|+|E|) with adjacency lists; only BFS guarantees the minimum edge count here.
Rearrangements
Runtime with adjacency lists
For a full traversal of the reachable graph.
Task variant
Use the example for Graph search: BFS, DFS and shortest paths to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
Breadth-first search (BFS) explores an unweighted graph by layers and finds shortest paths by edge count; depth-first search (DFS) follows a path deeply before backtracking.
The relation applies only under its stated assumptions.
In the unweighted graph s–a, s–b, a–t, b–c, c–t, what distance does BFS return from s to t?
BFS finds s–a–t with two edges, so d(s,t)=2.
DFS that visits b first may discover t through s–b–c–t after three edges; DFS does not guarantee a shortest path.
Common mistakes
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: BFS uses a FIFO queue and discovers vertices in nondecreasing distance from the start. It therefore finds shortest paths in unweighted graphs or graphs with equal edge costs; with unequal.
Exam context
- Compute unweighted shortest paths, reachability and graph traversals, and explain their operation counts.
Formula cluster
Graphs and algorithms
Breadth-first search (BFS) explores an unweighted graph by layers and finds shortest paths by edge count; depth-first search (DFS) follows a path deeply before backtracking.
Worked example
Consider edges s–a, s–b, a–t, b–c and c–t. BFS finds d(s,t)=2 via s–a–t. If DFS explores b before a, it may first discover t via s–b–c–t, a three-edge route. Both searches take O(|V|+|E|) with adjacency lists; only BFS guarantees the minimum edge count here.
Applications
Compute unweighted shortest paths, reachability and graph traversals, and explain their operation counts.
How do you calculate with Graph search: BFS, DFS and shortest paths?
Here is how to work through a typical Graph search: BFS, DFS and shortest paths (BFS: distance layers and shortest paths; BFS/DFS: O(|V|+|E|)) task step by step:
- 1
Task
Use the example for Graph search: BFS, DFS and shortest paths to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
Breadth-first search (BFS) explores an unweighted graph by layers and finds shortest paths by edge count; depth-first search (DFS) follows a path deeply before backtracking.
The relation applies only under its stated assumptions.
- 2
Task
In the unweighted graph s–a, s–b, a–t, b–c, c–t, what distance does BFS return from s to t?
Solution path
BFS finds s–a–t with two edges, so d(s,t)=2.
DFS that visits b first may discover t through s–b–c–t after three edges; DFS does not guarantee a shortest path.
Frequently asked questions about Graph search: BFS, DFS and shortest paths
How do BFS and DFS differ?+
Breadth-first search stores discovered vertices in a FIFO queue and processes all vertices at one distance before moving farther away. Depth-first search follows an unvisited neighbor using a stack or recursion until that branch has no new neighbor, then backtracks. Both find reachable vertices and can inspect connectivity or components. Their visitation order also depends on neighbor ordering. Only BFS has a general shortest-path guarantee for unweighted edges. Assumption: finite graph stored as adjacency lists; BFS guarantees shortest paths only for equal edge costs.
When is a BFS path actually shortest?+
BFS discovers vertices in increasing order of their edge count from the start. When t is first reached, no undiscovered route with fewer edges can remain, because all shorter layers have already been processed. This guarantee holds for unweighted graphs or equal-cost edges. If edges carry different distances or costs, minimizing the edge count need not minimize total cost. Use a weighted method such as Dijkstra instead; negative edges require additional assumptions and different algorithms. Assumption: finite graph stored as adjacency lists; BFS guarantees shortest paths only for equal edge costs.
Why is the runtime O(|V|+|E|)?+
With adjacency lists, each reachable vertex is marked and put on the queue or stack at most once. When removed, the search inspects its neighbor entries; across all vertices, the lists contain O(|E|) entries. The work is therefore O(|V|) for vertices plus O(|E|) for edges. In a directed graph, E counts directed edges. An adjacency matrix instead checks many possible neighbors for each visited vertex and typically costs O(|V|2). Assumption: finite graph stored as adjacency lists; BFS guarantees shortest paths only for equal edge costs.
How do the example distances of two and three arise?+
In the graph with edges s–a, s–b, a–t, b–c and c–t, t lies in BFS layer two: s has distance 0, a and b distance 1, and t is reached via a at distance 2. If DFS chooses b first, it follows c to t and may first discover t after three edges. The DFS tree depends on neighbor order; a later route may be shorter even if DFS does not find it first. Assumption: finite graph stored as adjacency lists; BFS guarantees shortest paths only for equal edge costs.
When is DFS still the right search?+
DFS is useful for reachability, connected components, cycles, topological ordering in directed acyclic graphs, or exploring a search tree. It typically stores the current path and open branches rather than an entire distance frontier. That can be practical, but DFS guarantees neither the shortest unweighted path nor shallow recursion. For very deep graphs, an iterative stack can avoid call-stack overflow. Choose the search for the question being asked, not only for its asymptotic runtime. Assumption: finite graph stored as adjacency lists; BFS guarantees shortest paths only for equal edge costs.
Quanta exam set
Curated exam set for "Graph search: BFS, DFS and shortest paths":
Question (front)
Which formula describes Graph search: BFS, DFS and shortest paths?
Answer in your set
Question (front)
How do you rearrange Graph search: BFS, DFS and shortest paths for Runtime with adjacency lists?
Answer in your set
Question (front)
Which common mistake happens with Graph search: BFS, DFS and shortest paths?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
Subject references and further reading
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
More formulas: Algorithms, number representation and cryptography
Retain Graph search: BFS, DFS and shortest paths for exams
Create a curated FSRS exam set for BFS: distance layers and shortest paths; BFS/DFS: O(|V|+|E|): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential