31251 Lec 11.1: Job scheduling and topological sort

We introduce the definition of a topological sort of a directed graph. We motivate topological sort by looking at its application the problem of job scheduling, or navigating your way through coursework while respecting the prerequisite constraints. A topological sort exists if and only if the graph does not have a directed cycle, as we will show in a later video. In this video we look at graphs without any directed cycles, known as directed acyclic graphs as DAGs, and compare/contrast them with undirected graphs that have no cycles.