Chapter 6: Breadth-first search
The chapter introduction presents breadth-first search as a way to find shortest distances and shows that “shortest” can mean different things in different applications.
After this chapter you will be able to
- Different meanings of shortest distance. Explain that breadth-first search can find the shortest distance between two things, and give an example of what distance can mean in a particular problem.
- Shortest path by step count. Explain why checking whether the bridge is reachable in one step, then two, then three establishes that the shortest route shown takes three steps. Describe this as a shortest-path problem that can be modeled as a graph and solved with breadth-first search.
- Graph nodes and edges. Explain that a graph models connections between things using nodes and edges, as in a graph showing who owes whom poker money.
- Direct neighbor directions. Distinguish in-neighbors from out-neighbors using the direction of a direct connection: because Alex points to Rama, Alex is Rama’s in-neighbor and Rama is Alex’s out-neighbor.
- Expanding the mango seller search. Trace how the mango-seller search starts with your friends and expands through their friends as each person is checked.
- Closest seller by connection degree. Explain why breadth-first search finds the closest mango seller: it checks first-degree connections before second-degree connections, then continues outward.
- Search list insertion order. Explain why people must be searched in the order they were added to the search list, and state that a queue provides this ordering.
- Queue operations and search order. Explain how enqueue and dequeue make a queue first in, first out, and why that makes breadth-first search examine people in the order they were added to its search list. Distinguish this order from a stack’s last-in, first-out order.
- Graph adjacency representation. Explain how a hash table represents a graph by mapping each node to an array of its out-neighbors, and describe what looking up a node returns.
- Directed and undirected neighbors. Distinguish a directed graph’s in-neighbors and out-neighbors from the simpler neighbor relationship in an undirected graph.
- Queue Based Seller Search. Trace how the search starts with your out-neighbors in a queue, checks people with person_is_seller, adds their out-neighbors, and stops when it finds a seller or the queue is empty.
- Searched People Set. Explain why the search keeps a set of people already checked and consults it before checking someone again.
- Breadth-first search running time. Explain why breadth-first search takes O(V+E) time when searching the entire network: it follows the edges and adds people to the queue.
- Paths and shortest-path modeling. Explain that breadth-first search can determine whether a path exists from A to B and find the shortest path if one exists. Describe when to try modeling a problem as a graph.
- Queue order and repeat checks. Explain why the search list must be a queue and why someone already checked should not be checked again.
What it builds on
- The stack (chapter 3) · The contrast assumes familiarity with a stack.
- Hash functions (chapter 5) · A hash table maps keys to values.
Section by section
Introduction
The chapter introduction presents breadth-first search as a way to find shortest distances and shows that “shortest” can mean different things in different applications.
- Different meanings of shortest distance: Explain that breadth-first search can find the shortest distance between two things, and give an example of what distance can mean in a particular problem.
Why it matters: Recognizing what “shortest” means in a problem helps you see where breadth-first search might be useful.
Key terms: breadth-first search, shortest distance
6.1 Introduction to graphs
The section uses a bus-route example to introduce shortest-path problems and the high-level role of graphs and breadth-first search in solving them.
- Shortest path by step count: Explain why checking whether the bridge is reachable in one step, then two, then three establishes that the shortest route shown takes three steps. Describe this as a shortest-path problem that can be modeled as a graph and solved with breadth-first search.
Why it matters: It connects the concrete bus-route question to the shortest-path problem addressed in the rest of the chapter.
Key terms: shortest-path problem, graph, breadth-first search
6.2 What is a graph?
This section introduces graphs as models of connections and explains nodes, edges, and direct in-neighbor and out-neighbor relationships using poker debts.
- Graph nodes and edges: Explain that a graph models connections between things using nodes and edges, as in a graph showing who owes whom poker money.
Why it matters: Nodes and edges are the basic vocabulary for describing the graphs used throughout the chapter. - Direct neighbor directions: Distinguish in-neighbors from out-neighbors using the direction of a direct connection: because Alex points to Rama, Alex is Rama’s in-neighbor and Rama is Alex’s out-neighbor.
Why it matters: Direction and direct connection determine which nodes count as neighbors.
Key terms: graph, nodes, edges, in-neighbor, out-neighbor, directly connected
6.3 Breadth-first search
The section introduces breadth-first search as a graph search and uses a mango-seller example to show how it explores a network.
- Two graph search questions: Distinguish the two questions breadth-first search can help answer: whether a path exists between two nodes and what the shortest path between them is.
Why it matters: These questions clarify what the search is trying to find before considering how it proceeds. - Expanding the mango seller search: Trace how the mango-seller search starts with your friends and expands through their friends as each person is checked.
Why it matters: The example shows how breadth-first search can look beyond immediate connections to find someone in a network.
Key terms: breadth-first search, path, shortest path, node, list, friends, friends’ friends, mango seller
6.4 Finding the shortest path
This section explains why breadth-first search finds the closest mango seller and why checking people in the order they were added is necessary.
- Closest seller by connection degree: Explain why breadth-first search finds the closest mango seller: it checks first-degree connections before second-degree connections, then continues outward.
Why it matters: Checking nearby connections first is what makes the first seller found the closest one. - Search list insertion order: Explain why people must be searched in the order they were added to the search list, and state that a queue provides this ordering.
Why it matters: Finding the nearest seller depends on checking people in the right order, not just adding them to a list.
Key terms: breadth-first search, shortest path, first-degree connections, second-degree connections, search list, queue
6.5 Queues
Explains how a FIFO queue determines the order in which breadth-first search examines people on its search list.
- Queue operations and search order: Explain how enqueue and dequeue make a queue first in, first out, and why that makes breadth-first search examine people in the order they were added to its search list. Distinguish this order from a stack’s last-in, first-out order.
Why it matters: The queue’s ordering explains why breadth-first search checks earlier additions before later ones.
Key terms: queue, enqueue, dequeue, FIFO, LIFO, stack
6.6 Implementing the graph
Shows how to represent a graph in Python with a hash table and distinguishes directed from undirected neighbor relationships.
- Graph adjacency representation: Explain how a hash table represents a graph by mapping each node to an array of its out-neighbors, and describe what looking up a node returns.
Why it matters: This representation makes a node’s outgoing connections available to the search algorithm. - Hash table entry order: Explain why the order of adding the graph’s key/value pairs does not matter.
Why it matters: The graph representation does not depend on writing its entries in a particular sequence. - Directed and undirected neighbors: Distinguish a directed graph’s in-neighbors and out-neighbors from the simpler neighbor relationship in an undirected graph.
Why it matters: The distinction tells you whether a connection points out from a node or simply joins two nodes.
Key terms: graph, node, out-neighbors, hash table, hash tables, key/value pairs, directed graph, undirected graph, in-neighbor, out-neighbor
6.7 Implementing the algorithm
This section shows how breadth-first search uses a queue to check people for a mango seller and a searched set to avoid repeated checks and loops.
- Queue Based Seller Search: Trace how the search starts with your out-neighbors in a queue, checks people with person_is_seller, adds their out-neighbors, and stops when it finds a seller or the queue is empty.
Why it matters: The queue and stopping conditions explain what the search does at each step. - Searched People Set: Explain why the search keeps a set of people already checked and consults it before checking someone again.
Why it matters: Tracking checked people keeps shared friends and cycles from making the search repeat work.
Key terms: search queue, out-neighbors, person_is_seller, mango seller, searched, set
6.8 Running time
This section derives breadth-first search’s O(V+E) running time and introduces topological sorting and trees through graph exercises.
- Breadth-first search running time: Explain why breadth-first search takes O(V+E) time when searching the entire network: it follows the edges and adds people to the queue.
Why it matters: The bound accounts for both the connections searched and the people added to the queue. - Dependency-based task ordering: Describe how a topological sort makes an ordered list from a graph of dependent tasks, placing each task after tasks it depends on while allowing more than one valid order.
Why it matters: It turns task dependencies into a usable order without insisting on one unique list. - Family tree graph structure: Explain why the family tree in this section is a graph and what makes it a tree.
Why it matters: The family example shows how a tree is distinguished from a general graph here.
Key terms: breadth-first search, O(V+E), vertices, edges, queue, topological sort, depends on, tree, graph, nodes
6.9 Recap
Recaps how breadth-first search finds paths in graphs, why a queue preserves shortest-path results, and why checked nodes must not be revisited.
- Paths and shortest-path modeling: Explain that breadth-first search can determine whether a path exists from A to B and find the shortest path if one exists. Describe when to try modeling a problem as a graph.
Why it matters: This helps you recognize problems where breadth-first search may be useful. - Directed and undirected relationships: Distinguish directed from undirected graphs by explaining whether a relationship follows an arrow or goes both ways.
Why it matters: The kind of graph determines which connections the relationships represent. - Queue order and repeat checks: Explain why the search list must be a queue and why someone already checked should not be checked again.
Why it matters: The queue preserves the shortest-path result, while avoiding repeat checks keeps the search from looping indefinitely.
Key terms: breadth-first search, shortest path, graph, directed graph, undirected graph, queue, FIFO, stack, LIFO, search list
Where this is used later
- File Directories (chapter 7) · Introduces breadth-first search as a graph algorithm.
- Recap (chapter 7) · Breadth-first search introduces graph traversal and shortest-path finding.
- Linear programming (chapter 13) · Earlier discussion of graph algorithms provides the examples being related to linear programming.
- A space odyssey: Depth-first search (chapter 7) · Finding a shortest path with breadth-first search.
- (chapter intro) (chapter 9) · Finding a shortest path by counting segments.
- Implementation (chapter 9) · Representing a graph’s out-neighbors in a hash table.
- A better definition of trees (chapter 7) · Provides the initial description of a tree that the later definition develops.
- Working with Dijkstra’s algorithm (chapter 9) · Provides a point of comparison for another path-finding algorithm.
Concepts explained in this chapter
- breadth-first searchBreadth-first search is a graph-search algorithm that explores vertices in increasing order of their distance from a starting vertex.
- graphA graph is a data structure consisting of nodes and connections that represent relationships between entities.
- shortest pathA shortest-path problem asks for a path between locations or nodes that minimizes the number of steps or another path cost.
- edgeAn edge is a connection between two vertices in a graph, optionally representing a direction from one vertex to another.
- setA set is a collection that stores distinct elements without assigning significance to their insertion order.
- performanceBig O notation is a mathematical notation for describing the asymptotic growth rate of an algorithm's resource usage as input size increases.
- treeA tree is a connected graph with no cycles, so no path of edges leads back to an earlier vertex.
- MapA dictionary is a Python mapping data structure that associates keys with corresponding values.
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.