shortest paths in number of edges

Sometimes the only cost that matters is how many steps a journey takes, not how long each step is. How many friend-of-a-friend links separate two people? What is the fewest moves a knight needs to cross a chessboard? How many clicks from one Wikipedia article to another? In all of these every edge counts as one, and the shortest path is simply the one with the fewest edges. This is the natural distance in an unweighted graph, and breadth-first search computes it exactly.

BFS does it by reaching vertices in order of increasing distance. Give the source distance 0; when BFS first discovers a vertex v through an edge from u, it sets dist(v) = dist(u) + 1. The reason this is correct, not just plausible, is the queue invariant: BFS processes all distance-k vertices before any distance-(k+1) vertex, so the first time any vertex is discovered it is being discovered from the closest possible ring — there is no shorter route waiting to be found later. You can prove dist(v) is exactly the true shortest distance by induction on the distance: it holds at distance 0, and if every vertex at distance k gets the right value, then each of their undiscovered neighbours is genuinely at distance k+1 and BFS labels it so. Following parent pointers back from v to the source reconstructs an actual fewest-edge path, not just its length.

This is the workhorse behind 'degrees of separation', shortest-move puzzles, network hop counts, and as a subroutine inside bigger algorithms. It costs O(n + m) on an adjacency list — linear, and you cannot do better since you may have to look at the whole graph. The essential caveat: this is fewest edges, which equals cheapest path only when all edges cost the same. The moment edges carry different weights, BFS gives the wrong answer for cheapest cost, and you must switch to Dijkstra (nonnegative weights) or Bellman-Ford (general weights). A useful middle case: if weights are small integers you can sometimes still use a BFS-like method by splitting heavy edges, but the clean statement is that plain BFS solves the unweighted case.