Graph Traversal Overview

Math for CS · Axiom Academy

LESSON Graph Traversal: BFS and DFS Two fundamental strategies for exploring every vertex in a graph A graph traversal (or graph search) is an algorithm that visits every vertex in a graph exactly once, following edges to move from vertex to vertex. Traversal is the backbone of almost every graph algorithm. Traversal Problem: Given a graph and a starting vertex , visit all vertices reachable from in a systematic order. There are exactly two classical strategies, and they differ in one simple choice: which discovered-but-unexplored vertex do we visit next? Breadth-First Search (BFS) — visit the oldest discovered vertex first (uses a queue ). Depth-First Search (DFS) — visit the newest discovered vertex first (uses a stack ). That single data-structure swap produces dramatically different exploration patterns and unlocks different applications. BFS: Level-by-Level Exploration BFS explores a graph in concentric "waves" outward from the source. It visits all neighbors of first, then all vertices two edges away, then three, and so on. Key property: BFS discovers every vertex at its shortest distance (fewest edges) from the source. This makes BFS the go-to algorithm for shortest paths in unweighted graphs . Enqueue the start vertex and mark it visited. Dequeue a vertex . For each unvisited neighbor of , mark visited and enqueue it. Repeat until the queue is empty. Shortest path in unweighted graphs Testing bipartiteness (two-colorability) Level-order traversal of trees

This is the written version of the interactive lesson above. See the full Math for CS course.