Breadth-First Search

noun

say it: “BREDTH FURST SURCH” /brɛdθ fɜrst sɜrtʃ/

A way of exploring a graph one level at a time from a starting point, which finds the fewest steps to each place.

What is breadth-first search?

Breadth-first search (BFS) explores a graph level by level: every vertex one step from the start, then every vertex two steps away, and so on, like ripples spreading in a pond. A queue keeps the order and a visited set stops repeats. The first time it reaches a vertex is by the fewest steps.

In a sentence

  • “The subway app runs a breadth-first search from your station to find the route with the fewest stops.”

Level: Journeyman · More Data Structures terms at this level

Updated