Depth-First Search

MIT 6.006 Introduction to Algorithms, lecture 10, 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 reviews what a graph is, explains what linear time means, and introduces depth-first search and the reachability problem.

Key ideas

A graph is a set of vertices (dots, also called nodes) joined by edges (lines or arrows between dots). Each edge is a pair of vertices, one 'from' and one 'to'. 0:57
When computer scientists say an algorithm runs in linear time, they mean its running time grows in step with the size of the input. For a graph, that size is the number of vertices plus the number of edges. 5:14
Breadth-first search explores in rings: every vertex one step away, then every vertex two steps away, and so on. Depth-first search does the opposite: it follows one path as far as it can go, then backs up and tries another. 6:37
The reachability problem asks which vertices you can get to from a starting vertex by following edges. A vertex whose edges all point away from the start cannot be reached. 8:24
To prove a vertex can be reached, you can store each vertex's previous vertex on the way in. Starting at the target and following those links back to the start, then reversing the list, gives you a valid path. 9:28

Words to know

vertex: A point in a graph. It is also called a node. Think of it as a dot.
edge: A connection between two vertices. In a directed graph it is an arrow with a direction, so you can only travel one way along it.
linear time: A way of describing speed: the work grows at the same rate as the size of the input. Double the input, and the work roughly doubles.
reachability: Whether you can get from a starting point to another point by following the allowed connections, such as edges in a graph.

Example

Imagine a town where intersections are vertices and one-way streets are edges. Reachability asks which intersections you can drive to from your house without breaking any traffic rules. Breadth-first search would check every place one turn away, then two turns away. Depth-first search would keep driving down one street as far as it goes, then turn back at a dead end.

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

Part 2 · 10:00–20:00

This part explains depth-first search, a method that starts at a source node and follows paths as far as it can to find every node that can be reached from that source, and then proves the method works.

Key ideas

The reachability problem asks which nodes you can get to from a starting point, the source. A parent tree records, for each node, the node that led to it, but the path it traces does not have to be the shortest one. 10:00
Depth-first search marks the source, then goes through each outgoing edge. For each neighbor it has not visited yet, it sets that neighbor's parent to the current node and visits that neighbor recursively, which means the function calls itself. 11:27
Depth-first search goes all the way down one path to the end, then backs up and tries the next option. Breadth-first search instead finishes one whole level before moving further out. 13:36
The correctness proof uses induction on the distance from the source. The base case is the source itself, and the inductive step shows that each node one step further away gets the correct parent. 15:06
The proof shows that when a node u is visited, each neighbor v either already has a parent or gets one from the current line of code. Either way, the result is correct, so calling visit on the source finds every reachable node. 19:21

Words to know

reachable: A node is reachable from a source if there is some route of edges that gets you from the source to that node.
parent tree: A record that stores, for each node, which node you came from to reach it. Following the links backward traces a route to the source.
recursion: When a function calls itself to handle a smaller piece of the same job, like a set of nested boxes opened one inside another.
induction: A proof method. You show the claim is true for the starting case, then show that if it is true for one step, it is true for the next step.

Example

Think of exploring a maze with a ball of string. You walk down one corridor as far as it goes, and when you hit a dead end you walk back to the last junction and try a different corridor. Depth-first search works the same way, always going deep before it comes back to try other options.

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

Part 3 · 20:00–30:00

Depth-first search explores a graph by going as deep as it can along one path, and this lesson shows how it can be used to find the separate clumps of connected vertices in a graph.

Key ideas

Depth-first search (DFS) starts at a source vertex and recursively visits its neighbors, then their neighbors, and so on. It only ever reaches vertices that can be reached from the source. 24:56
Each vertex is visited at most once, so each edge is looked at at most once. Because of this, DFS takes order e time (where e is the number of edges), and it does not need to look at every vertex the way breadth-first search does. 21:01
The path DFS finds is not guaranteed to be the shortest. On a loop-shaped graph, DFS can take the long way around even when a shorter edge is available. 24:14
Full DFS finds every connected component in an undirected graph. It loops over all vertices, and whenever it finds one that has not been visited yet, it starts a DFS from there to collect that whole clump. 28:10

Words to know

reachable: You can get to it by following edges from where you start.
recursive: A function that calls itself to do part of the work, like a task that hands smaller versions of itself to helpers.
undirected graph: A graph where edges go both ways, so you can travel either direction along an edge.
connected component: A group of vertices where you can get from any one of them to any other, and which has no edges leading out to the rest of the graph.

Example

Imagine exploring a city by always taking the first street you see and walking as far as you can. When you hit a dead end, you turn back to the last fork and try another street. You will see every place you can reach, but the route you walked may be much longer than the shortest one.

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

Part 4 · 30:00–40:00

This part explains how depth-first search runs in linear time, how it finds separate groups in a graph, and how it can put the nodes of a special kind of graph (a DAG) into a valid order.

Key ideas

Depth-first search (DFS) runs in about v plus e steps, where v is the number of vertices (dots) and e is the number of edges (lines). This works because each edge is touched at most one time. 30:20
DFS can find connected components, which are separate groups of vertices linked to each other but not to anything outside the group. The lecture's example is two friends who are friends only with each other. 31:06
A DAG is a directed graph with no cycles, so you can never follow the arrows from a point and get back to where you started. 32:31
A topological order lists every vertex so that each directed edge goes from an earlier item to a later one. A graph can have more than one valid topological order. 34:39
For a DAG, if you run DFS and record the order in which each vertex finishes, then flipping that list gives a topological order. 36:53

Words to know

DAG: Directed Acyclic Graph: a set of dots joined by one-way arrows, with no loops that let you walk in a circle back to a starting dot.
topological order: A list of all the dots in a directed graph where every arrow points from a dot earlier in the list to a dot later in the list.
finishing order: The order in which DFS finishes visiting each dot, which is the moment all of that dot's neighbors have been checked.
connected component: A group of dots that can all reach each other through edges, and that has no edges linking it to the rest of the graph.

Example

Imagine a class where two students are friends only with each other. If you start a search at one of them and follow friendships, you will find just those two, and you know they form their own group. Doing this from every student finds every separate group in the class.

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

Part 5 · 40:00–52:18

This part shows how a depth-first search can put the nodes of a graph in a valid order and how it can detect and find a cycle.

Key ideas

If there is an edge from u to v, reverse finishing order puts u before v, because v finishes before u does. That is the main reason the reversed order works. 41:08
Reverse finishing order gives a topological order, which is a list of nodes where every edge points forward. Both cases in the proof keep every edge pointing the right way. 43:50
If the reversed order has an edge pointing backward, the graph cannot be a DAG. So checking the order also tells you whether the graph has a cycle. 45:43
If a graph has a cycle, a depth-first search always walks an edge from a node back to one of its ancestors, which is a node visited earlier in the search. 48:20
To return the actual cycle, you check for the backward edge while the search runs and stop as soon as you find one. 52:03

Words to know

DAG: Directed acyclic graph: a graph whose arrows point one way and never loop back to where they started.
topological order: A list of all the nodes where every arrow goes from an earlier node in the list to a later one.
cycle: A path of arrows that starts at one node and comes back to that same node.
ancestor: A node that was visited earlier in the search's chain of calls, before the node you are looking at.

Example

Think of getting ready for work: you must put on socks before shoes, and a shirt before a jacket. A valid order lists each task after the ones it depends on. If two tasks each had to come before the other, no valid order would exist, just like a cycle in a graph.

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

← Lecture 9: Breadth-First Search · Lecture 11: Weighted Shortest Paths →

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