Breadth-First Search

MIT 6.006 Introduction to Algorithms, lecture 9, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces graphs, which are simple sets of dots connected by lines, and shows how many everyday problems can be described this way.

Key ideas

A graph is a collection of two things: vertices, which are the points or nodes, and edges, which are the connections between them. 2:01
Each edge is just a pair of vertices that it links together. The fancy math notation is only a formal way of saying this. 2:23
In a directed graph, an edge has a direction, like a one-way street, so going from A to B is not the same as going from B to A. In an undirected graph, edges have no direction. 3:46
Graphs are everywhere in daily life, including computer networks, social networks, road maps, and the possible states of a Rubik's cube. 5:12
In a map of voting precincts, you can make a graph by drawing a node for each precinct and an edge wherever two precincts share a boundary. 8:46

Words to know

vertex: A point or dot in a graph. Vertices are also called nodes. In a computer network, each computer could be one vertex.
edge: A connection between two vertices. In a computer network, an edge is roughly a cable linking two computers.
directed graph: A graph where each connection has a direction, like a one-way street. You can only travel an edge in the direction it points.
undirected graph: A graph where connections have no direction, like a two-way road. If A is connected to B, then B is connected to A.

Example

Think of a city map where each intersection is a dot and each road between intersections is a line. If some roads are one-way, the map is like a directed graph, and you can only drive the way the arrows point. If all roads are two-way, the map is like an undirected graph.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains what makes a graph 'simple,' how many edges a graph can have, and what neighbors and degree mean.

Key ideas

A simple graph has no self loops (an edge from a vertex back to itself) and no repeated edges. The lecturer treats graphs as simple from now on. 10:22
Because of these rules, the number of edges is limited. In an undirected graph, the most edges is the number of ways to pick 2 vertices from V. A directed graph can have twice that, because an edge from v to w is different from an edge from w to v. 12:36
Since both limits are roughly V squared, the number of edges is at most about V squared. Many real graphs are sparse, meaning they have far fewer edges than that maximum, so an algorithm that scales with the number of edges can be much faster. 14:44
A vertex's neighbors are the vertices connected to it by an edge. For directed graphs, the outgoing neighbors point away from the vertex and the incoming neighbors point toward it. The degree of a vertex is the number of edges in one of these sets. 17:37
Degree matters because many algorithms loop over every neighbor of a vertex. Knowing the total of all degrees tells you roughly how much work those loops will take. 18:25

Words to know

simple graph: A graph with no edge that starts and ends at the same vertex, and no two identical edges between the same pair of vertices.
degree: How many edges touch a vertex. In a directed graph, out degree counts edges leaving it and in degree counts edges coming in.
sparse: Having relatively few edges compared with the most edges the graph could have.
binomial coefficient: A count of how many ways you can choose a set number of items from a group when the order does not matter. Here, V choose 2 counts the unique pairs of vertices.

Example

Think of a town where houses are vertices and roads are edges. A simple town map has at most one road between any two houses, and no road that leads from a house straight back to itself. The number of roads is then limited by how many pairs of houses there are, just like the edge limit in a simple graph.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains three ways to store a graph on a computer, and then defines what a path and a shortest path are.

Key ideas

An edge list is the simplest way to store a graph, but checking whether one specific edge exists means looking through the whole list, which can take a long time. 22:13
An adjacency list stores, for each vertex, the set of vertices it connects to. If that set is a hash table, checking whether an edge exists takes about the same short time no matter how big the graph is. 24:22
Whether you keep outgoing or incoming edges is a design choice, so pick the one that fits what your algorithm needs to do. 25:02
An adjacency matrix makes checking for an edge very easy, but looping over a vertex's neighbors means scanning every vertex, and it uses more space. 26:07
A path is a sequence of vertices where each pair of neighboring vertices is joined by an edge. Its length is the number of edges, and a shortest path is the one with the fewest edges. 28:54

Words to know

adjacency list: A way to store a graph where each vertex keeps a list of the vertices it is directly connected to.
adjacency matrix: A big grid with one row and one column for each vertex, where each box says yes or no for whether two vertices are connected.
hash table: A storage method that jumps straight to the place where an item should be, so looking things up is very quick.
shortest path: The route between two points that uses the fewest edges, like the quickest set of streets between two intersections.

Example

Think of a graph as a road network, where each vertex is an intersection and each edge is a road between two intersections. A path is a route you could drive from one intersection to another, and the shortest path is the route that passes through the fewest roads. The lesson uses this picture to show why the length of a path counts the roads, not the intersections.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains why a path between two points is not guaranteed, how one problem can be solved using another, and how a shortest path tree lets you rebuild shortest paths using very little storage.

Key ideas

Not every graph is connected. A graph with 10 vertices and no edges is valid, so the answer to 'is there a path?' can be no. 30:00
Reduction means using one solved problem to solve another. If you can find shortest path lengths, you can answer the yes-or-no path question: an infinite length means no path. 31:03
The lecture focuses on single source shortest path, the hardest of the three problems, because solving it also solves the easier ones. 32:07
Instead of storing every full path, you store one predecessor for each vertex, which is the vertex just before it on the shortest path. This is the shortest path tree. 35:57
The shortest path tree takes only linear space, about one entry per vertex. To rebuild a path, you start at the target and keep following predecessors back to the start. 38:31

Words to know

reachability: Whether you can get from one point to another by following edges. The answer is yes or no.
reduction: Solving one problem by calling code that already solves a different problem.
predecessor: The vertex that comes right before a given vertex on a path.
shortest path tree: A record that stores, for each vertex, only its predecessor on the shortest path from the start, so the full paths can be traced backward.

Example

Think of a road map where you want the shortest route from your home to every town. Instead of writing down every full route, you write one note per town saying which town you passed just before it. To get back to your home from any town, you follow the notes backward one step at a time. This is only an illustration of the idea, not something the lecture says.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–52:46

This part shows how Breadth-First Search finds shortest paths from one starting vertex by building groups of vertices, one distance at a time.

Key ideas

A shortest path can change when even one edge is added, so an old shortest-path tree may stop being correct. The lesson treats this as a real problem: any change to the graph or source means recomputing everything. 40:00
A level set L_k is the group of all vertices exactly k steps away from the source vertex. Once you have these groups, you can read off how far each vertex is. 42:04
Breadth-First Search builds the level sets one at a time. It starts with the source, then uses each level to find the next level's neighbors, and it never adds a vertex to a second level. 45:17
While building each level, the algorithm records each vertex's distance and its previous vertex, which is the step before it on the shortest path. 48:43
The running time is proportional to the number of vertices plus the number of edges. The lesson calls this linear time in the size of the stored graph. 51:36

Words to know

level set: A group of all the vertices that are the same number of steps away from a starting point.
source vertex: The starting vertex that all distances are measured from.
adjacent: Directly connected by one edge to a given vertex. The lesson uses it for the neighbors of a vertex.
big O: A way of describing how an algorithm's running time grows as the input gets bigger, ignoring fixed constant factors.

Example

Think of dropping a stone in a pond. The ripple reaches every spot at distance 1 first, then every spot at distance 2, and so on. Breadth-First Search works the same way: it reaches all the vertices one step away before any two steps away.

3 checked practice questions for this part are in the app.

← Lecture 8: Binary Heaps · Lecture 10: Depth-First Search →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York