Opening Depth-First Search (DFS) (MIT 6.006, Recitation 14)
Depth-First Search (DFS) (MIT 6.006, Recitation 14)
- Length
- 54 min
- Level
- Undergraduate
- Recorded
- MIT2013
Chapter 1 of 8: Before the lecture
Depth-first search explores a graph by following each branch as far as it goes before backtracking. Costan starts from adjacency lists written as Python dictionaries and builds a recursive traversal that uses parent pointers to avoid revisiting vertices. Tracing a directed graph by hand, he classifies each edge as a tree, forward, backward or cross edge relative to the search tree. He then shows why undirected graphs produce only tree and backward edges. The recitation closes with topological sort on a directed acyclic graph of class prerequisites, obtained by reversing the order of finishing times. Basic Python, recursion and graph vocabulary are assumed.
Your comment is kept while you sign up.Sign in
Costan codes depth-first search in Python, then reverses its finishing times to sort class prerequisites.
Depth-first search explores a graph by following each branch as far as it goes before backtracking. Costan starts from adjacency lists written as Python dictionaries and builds a recursive traversal that uses parent pointers to avoid revisiting vertices. Tracing a directed graph by hand, he classifies each edge as a tree, forward, backward or cross edge relative to the search tree. He then shows why undirected graphs produce only tree and backward edges. The recitation closes with topological sort on a directed acyclic graph of class prerequisites, obtained by reversing the order of finishing times. Basic Python, recursion and graph vocabulary are assumed.
This lecture
Lecture 28 of 31 of Introduction to Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.