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 vertex s, 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...