Graph Theory37 sections · 1633 units
Open in Course

Intro

Getting Dressed

Imagine you are getting dressed. You must put on socks before shoes. You must put on underwear before pants. You must put on a shirt before a jacket. You cannot put on shoes first. A topological sort is a linear ordering of tasks that respects all of these dependency rules.

If ABA \to B means "AA must come before BB", then AA appears before BB in the sorted list. Given a directed graph of dependencies, your goal is to find an order that satisfies every edge. This section will show you how.

What does a cycle mean here?