ConceptTheory & Algos
Topological sort
A linear ordering of vertices in a directed acyclic graph such that for every directed edge uv, vertex u comes before vertex v in the ordering.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Directed acyclic graph4Cycle2Graph traversal2Acyclic graphs1Depth-first search1DFS1DFS visit1Directed graph1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
5Each in their own terms, from the easiest level.
Erik Demaine
An ordering of vertices in a directed acyclic graph such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.Victor Costan
An ordering of vertices in a directed graph such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.Andrej Karpathy
A linear ordering of vertices in a directed acyclic graph such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.Marten van Dijk
A topological sort of a poset is a total order that is consistent with the partial order.
Lectures that assume it
2Connections
16The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Directed acyclic graph
- Cycle
- Depth-first search
- DAG shortest path beginning point
- Dynamic programming with Implicit graphs
- Prior sampling
Show 1 moreShow fewer
Lectures9
- Spelled-Out Intro to Neural Networks & Backpropagation: Building micrograd
- Depth-First Search (DFS), Topological Sort
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Dynamic Programming: All-Pairs Shortest Paths
- Relations, Partial Orders, and Scheduling
- Depth-First Search (DFS) (MIT 6.006, Recitation 14)