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 →
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 →
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 →
Related concepts
- depth-first searchcontrasts with · Depth-first search is a graph or tree traversal algorithm that explores one branch as far as possible before backtracking to explore alternatives.
- shortest pathaddresses · A shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
- queueuses · A queue is an ordered collection that holds items for retrieval or processing, typically removing them in the order they were added.
- traversalkind of · Traversal is the systematic process of visiting elements or nodes in a data structure according to its links, ordering, or a specified rule.
- algorithmkind of · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
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.