## Traversing a Graph

A common activity on a graph is visiting each vertex of it in a given order. We will start by introducing the breadth-first search, and then follow with depth-first search. Both of these techniques form the archetype for many important graph algorithms, as we will see later with the cycle detection and Dijkstra's algorithm for single-source shortest paths.

### Breadth-First Search

Given a graph*G = (V, E)*and a source vertexs, breadth-first search explores the edges of*G*systematically to discover every vertex that is reachable from*s*. While doing so, it computes the smallest number of edges from*s*to each reachable vertex, making it suitable to solve the single-source shortest path problem on unweighted graphs, or graphs whose edges all have the same weight.

**Breadth-First Search** (**BFS**)is named so because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. In that sense, the algorithm first explores vertices at distance*k*from...