Traversal
Graph traversal algorithms visit vertices and edges in a systematic order. They are the foundation for most other graph algorithms: shortest paths, connected components, and topological sort all build on BFS or DFS internally.
| Algorithm | When to use |
|---|---|
Unweighted shortest paths, level-by-level exploration. Finds the shortest hop count from a source to all reachable vertices. |
|
Cycle detection, topological sort, strongly connected components. Explores as deep as possible before backtracking. |
|
DFS on undirected graphs with proper back-edge classification. |
BFS uses a queue (FIFO). DFS uses a stack (LIFO, or recursion). Both have O(V + E) time complexity.
The _visit variants skip initialization and operate on a subset of
vertices — useful when you have already initialized colors or want to search
from a specific vertex without resetting state: