Breadth-first and depth-first traversal
Graph searches visit reachable vertices using different orders.
Key knowledge
BFS explores successive edge-distance layers; DFS follows unvisited neighbors and backtracks. With adjacency lists and constant-cost visited checks, full traversal runs in O(|V|+|E|). BFS yields unweighted shortest distances; DFS need not.
Conditions and scope
- A search from one source covers only reachable vertices; restart at unvisited vertices for full traversal.
- Representation and bookkeeping assumptions are part of the complexity bound.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Massachusetts Institute of Technology2 sources
Evidence and review
Graph definitions, adjacency representations, edge-count distances and BFS shortest paths. Depth-first reachability, full traversal, O(V+E) bound and distinction from BFS shortest paths.
2026-10-10 · BFS/DFS behavior, reachability and full-traversal cost.
Entry details
Permanent link to this entry ↗- Record identity
- info-graph-traversal
- Revision
- university-reference.1
- Structured reference record
- University reference