Sign inSign in

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.
as Srini Devadas defines itMITThe wording closest to all 7 definitions
Watch it explained

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

5

Each in their own terms, from the easiest level.

  • Erik Demaine

    MIT · Undergraduate

    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.
    • 41:56Depth-First Search (DFS), Topological Sort
    • 6:00Dynamic Programming: All-Pairs Shortest Paths
  • Victor Costan

    MIT · Undergraduate

    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.
    • 41:08Depth-First Search (DFS) (MIT 6.006, Recitation 14)
    • 16:04Dynamic Programming: Crazy Eights and Shortest Path (MIT 6.006, Recitation 19)
  • Andrej Karpathy

    Undergraduate

    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.
    • 1:18:18Spelled-Out Intro to Neural Networks & Backpropagation: Building micrograd
  • Marten van Dijk

    MIT · Undergraduate

    A topological sort of a poset is a total order that is consistent with the partial order.
    • 52:49Relations, Partial Orders, and Scheduling

Lectures that assume it

2

Connections

16

The lectures that define it or assume it, and the concepts next to it.

5 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.