Breadth-first search
Breadth-first search is a graph or tree traversal algorithm that explores nodes in nondecreasing order of their distance from a starting node.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A graph or state-space search algorithm that explores all states at the current distance before proceeding to greater distances.
- How it is used
- Finds shortest paths in fairly small graphs, demonstrated through maze solving.
- How deep it goes
- Works through a generic queue-based implementation, explored states, goal testing, and parent-linked path reconstruction.
- Examples
- Uses a randomly generated grid maze, four-way movement, and a printed path from start to goal.
- What you can do after
- Build it from scratch as a generic Swift search and apply it to mark a route through a maze.
Grokking Algorithms, Second Edition
Breadth-first search is a graph-search algorithm that explores vertices in increasing order of their distance from a starting vertex.
- How it is used
- Solves graph reachability and fewest-step path problems, then serves as a traversal method for directory trees.
- How deep it goes
- Walks through search order, queue and checked-set implementation, and O(V + E) runtime; the shown Python search returns a boolean rather than a route.
- Examples
- Uses a city route, a social-network mango seller, shortest-path exercises, and a file-directory listing.
- What you can do after
- Build it from scratch in Python with a deque and checked set, or adapt the queue-based traversal to list directory files.
Read how Grokking Algorithms, Second Edition explains breadth-first search →
Optimization Algorithms: AI techniques for design, planning, and control problems
Breadth-first search explores all reachable states at one depth before exploring states at greater depth.
- How it is used
- Uses blind graph traversal to discover routes or solutions without prior information about the search space.
- How deep it goes
- Explains queue operations, duplicate checks, route reconstruction, puzzle modeling, and rapidly increasing time and memory demands.
- Examples
- Demonstrates 8-puzzle solving, route reconstruction, path planning, and a Python run reporting time, memory, and explored states.
- What you can do after
- Apply BFS via Python to solve a modeled state-space problem and inspect its route, runtime, memory, and explored-state results.
Grokking Data Structures
Breadth-first search explores a graph level by level, visiting vertices in order of their distance from a starting vertex.
- How it is used
- Explores indirect relationships in a graph and finds paths with the minimum number of edges.
- How deep it goes
- Develops queue-based exploration step by step and provides Python code for searching and reconstructing a path.
- Examples
- Uses chains of social introductions to motivate finding the shortest path between two vertices.
- What you can do after
- Build it from scratch on a graph using a queue, distances and predecessors to return a path or report none.
Read how Grokking Data Structures explains breadth-first search →
Advanced Algorithms and Data Structures
Breadth-first search is a graph traversal algorithm that visits vertices in nondecreasing order of their distance in edges from a source vertex.
- How it is used
- Finds shortest paths from a known source when distance means the fewest traversed edges.
- How deep it goes
- Implements queue-based traversal with distances and parents, while deferring weighted shortest paths to Dijkstra’s algorithm.
- Examples
- Uses parcel delivery, grid-like street routes, shortest-path diagrams, and an edge-removal exercise.
- What you can do after
- Build it from scratch to traverse a graph, compute edge distances, detect a goal, and reconstruct a shortest route.
Read how Advanced Algorithms and Data Structures explains breadth-first search →
Algorithms Every Programmer Should Know
Breadth-first search is a graph or tree traversal algorithm that explores vertices level by level from a starting vertex.
- How it is used
- Traverses trees or graphs by exploring vertices layer by layer from a starting point.
- How deep it goes
- Explains queue-based traversal and complexity, with a Python tree implementation; does not detail a graph implementation.
- Examples
- Traces a search from root node 5 to node 8 and includes a level-order binary-tree implementation.
- What you can do after
- Apply BFS to traverse a binary tree in level order using a FIFO queue.
Read how Algorithms Every Programmer Should Know explains breadth-first search →
Grokking AI Algorithms, Second Edition
Breadth-first search is a search algorithm that explores a state tree level by level, processing all nodes at one depth before moving to the next.
- How it is used
- Uses unguided search to generate or traverse trees and find shortest paths when edges have equal cost.
- How deep it goes
- Explains queue operations, visitation, parent tracking, termination, and maze movement, but does not develop formal complexity analysis.
- Examples
- Uses a maze, movement tree, ripple analogy, queue trace, parent links, and a Python-style BFS function.
- What you can do after
- Apply BFS with a FIFO queue, visited tracking, neighbor generation, parent links, and a goal test.
Read how Grokking AI Algorithms, Second Edition explains breadth-first search →
Applied Reinforcement Learning
Breadth-first search explores graph or tree nodes in order of their distance from a starting node, typically using a FIFO queue.
- How it is used
- Uses BFS to explore delivery-route possibilities systematically before introducing more advanced search methods.
- How deep it goes
- Explains queue-based traversal and its guarantees, then flags memory costs and exhaustive routing limits.
- Examples
- Uses a depot-and-customer route tree to illustrate searching partial routes and comparing completed routes.
- What you can do after
- Apply BFS with a FIFO queue to search level by level and find minimum-step solutions when step costs are equal.
Read how Applied Reinforcement Learning explains breadth-first search →
Learn Haskell by Example
Breadth-first search explores a graph level by level from a starting node, visiting all nodes at one distance before proceeding to the next.
- How it is used
- Solves the ladder game by finding shortest paths through a graph with uniformly weighted edges.
- How deep it goes
- Defines layered exploration, visited-node deletion, predecessor tracking, and path reconstruction through a complete implementation.
- Examples
- Uses a word-ladder graph, layered graph figures, predecessor diagrams, and Haskell search listings.
- What you can do after
- Build the algorithm and reconstruct shortest paths from predecessor data in directed graphs with uniform cost.
Read how Learn Haskell by Example explains breadth-first search →
Transformers in Action
Breadth-first search is a graph or tree traversal algorithm that explores all nodes at the current level before proceeding to the next level.
- How it is used
- Deploys BFS to explore graph, tree, beam-search, and Tree-of-Thoughts search spaces systematically.
- How deep it goes
- Defines level-order traversal and contrasts DFS, but stops short of a standalone low-level BFS implementation.
- Examples
- Uses maze paths, token-sequence trees, and the Game of 24 to illustrate breadth-first exploration.
- What you can do after
- Apply it via tree-of-thoughts-llm to generate, evaluate, and select candidate reasoning paths.
Read how Transformers in Action explains breadth-first search →
Also covered in
- AI Agents in Action
- Clojure: The Essential Reference
- Machine Learning Algorithms in Depth
- AI Agents in Action, Second Edition
- The Well-Grounded Data Analyst
- The Coder CafeIn early access (MEAP)
What to know first
- graphA graph is a mathematical structure consisting of vertices and edges that connect pairs of vertices to represent relationships or connections.
- nodeA node is a discrete element of a graph, tree, linked structure, network, or computing system that can represent an entity, state, or component and may connect to other elements.
- pathA path is an ordered sequence of connected elements that traces a route through a structure or defines a drawable line or shape.
- shortest pathA shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
Related concepts
- depth-first searchcontrasts with · Depth-first search is a traversal strategy that follows a branch as far as possible before backtracking to explore alternatives.
- queueuses · A queue is an ordered collection that holds items for retrieval or processing, commonly in first-in, first-out order.
- shortest pathaddresses · A shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
- traversalkind of · Traversal is the systematic process of visiting elements or nodes in a data structure according to a specified order or rule.
- algorithmkind of · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
- Edmonds-Karp algorithmused by · The Edmonds-Karp algorithm is the Ford-Fulkerson method specialized to select augmenting paths with breadth-first search.
Questions about breadth-first search
What is breadth-first search?
Breadth-first search is a graph or tree traversal algorithm that explores nodes in nondecreasing order of their distance from a starting node.
Which Manning books explain breadth-first search?
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers, Grokking Algorithms, Second Edition, Optimization Algorithms: AI techniques for design, planning, and control problems, Grokking Data Structures, Advanced Algorithms and Data Structures, Algorithms Every Programmer Should Know, Grokking AI Algorithms, Second Edition, Applied Reinforcement Learning and 2 more.
What should I know before learning breadth-first search?
Manning books that teach breadth-first search usually introduce graph, node, path and shortest path first.
What is the difference between breadth-first search and depth-first search?
Breadth-first search is a graph or tree traversal algorithm that explores nodes in nondecreasing order of their distance from a starting node. Depth-first search is a traversal strategy that follows a branch as far as possible before backtracking to explore alternatives.
What is breadth-first search a kind of?
Breadth-first search is a kind of traversal. Traversal is the systematic process of visiting elements or nodes in a data structure according to a specified order or rule.
What is breadth-first search also called?
Breadth-first search is also called BFS.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.









