Graph traversal overview
Traversal means systematically visiting vertices (and optionally edges) of a graph starting from one or more sources. Unlike a linear list, graphs can branch and revisit neighbors—so every serious traversal keeps a visited discipline to avoid infinite loops. This page contrasts the two dominant patterns—BFS and DFS—before the dedicated lessons.
- Why “visited” matters
- Breadth-first vs depth-first (idea + table)
- Time with adjacency lists
- Where traversal shows up next in this tutorial
1) Visited sets and cycles
In a graph with cycles, naive “walk edges forever” never terminates. Standard fix: mark each vertex when you first discover it—often a visited[] boolean array of size V, or a small color label (white / gray / black) for richer state in DFS analysis.
Starting from source s, both BFS and DFS explore only the connected component containing s unless you restart from every unvisited vertex to scan the whole graph.
Cycle example: A — B
| |
C — D ← without visited[], A→B→D→C→A repeats forever
2) Two strategies: layers vs going deep
Breadth-first search (BFS)
Explore in waves by distance (number of edges) from the source. Use a queue: dequeue the front vertex, enqueue unvisited neighbors. On an unweighted graph, BFS discovers shortest path length in edge count from the source.
Depth-first search (DFS)
From the current vertex, go to an unvisited neighbor and recurse (or use an explicit stack) before fully backing out. DFS walks one branch to the end, then backtracks—natural for connectivity, topological sorting on DAGs, and many recursive graph patterns.
3) BFS vs DFS — comparison
| Aspect | BFS | DFS |
|---|---|---|
| Container | Queue (FIFO) | Stack or recursion (LIFO) |
| Shape of exploration | Layer by layer from source | Deep along one path, then backtrack |
| Unweighted shortest path | Yes — minimum edge count from source | No guarantee without extra structure |
| Memory taste | Queue may hold many frontier vertices | Recursion depth up to O(V) (watch stack limits) |
| Common uses | Shortest steps, level-order ideas | Connectivity, cycles, topo sort, SCC building blocks |
4) Time complexity
With an adjacency list, both BFS and DFS visit each vertex once and scan each edge at most twice (once from each endpoint in undirected graphs)—total time O(V + E), space O(V) for the visited structure plus queue or stack frames.
With an adjacency matrix, scanning neighbors of one vertex costs O(V), so total becomes O(V²) unless the matrix is sparse in a structural sense.
5) Next in this tutorial
- BFS on graphs — queue implementation, shortest path in unweighted graphs.
- DFS on graphs — recursion vs stack, timestamps optional.
- Cycle detection — often DFS- or parent-based rules.
Key takeaway
Pick BFS when you care about minimum number of edges from a source (unweighted) or level-by-level expansion; pick DFS when recursion and backtracking match the problem (paths, cycles, DAG order). Both need a visited mechanism and run in O(V + E) with adjacency lists.
Next up: BFS on graphs · DFS on graphs · Graph types