Skip to content
Tutorials Center
My learning

Topics

Lesson 128 of 225 ยท Graphs

Topological Sort

Order tasks so every dependency comes first. Learn Kahn's algorithm, DFS topological sort, the course schedule problem and longest paths in a DAG.

You cannot put on your shoes before your socks, you cannot compile a program before the libraries it uses, and you cannot take Algorithms II before Algorithms I. Whenever tasks depend on other tasks, you need an order in which every task comes after everything it depends on. Finding such an order is called a topological sort.

Dependencies form a directed graph: an edge A -> B means "A must come before B". A valid order exists exactly when the graph has no cycle, so the input must be a DAG (directed acyclic graph). In this lesson you learn the two standard algorithms, Kahn's algorithm (repeatedly peel off tasks that have nothing left to wait for) and the DFS method (reverse the finishing order). Then you apply them to a course-schedule problem and to finding the longest path in a DAG, which is how project planners compute the minimum project time.

The goal

TEXT
wake --> shower --> dress --> leave
  |                             ^
  +----> coffee --> breakfast --+

One valid order:   wake, shower, coffee, dress, breakfast, leave
Another valid one: wake, coffee, breakfast, shower, dress, leave
Invalid:           wake, dress, shower, ...   (dress before shower)

A topological order is a line-up of all vertices such that for every edge u -> v, u appears before v. There is usually more than one valid order. If the graph is a single chain there is only one; if there are no edges, every permutation works.

Kahn's algorithm: peel off the free tasks

Think about which task you can do first. It must be a task that does not wait for anything: a vertex with in-degree 0 (no incoming edges). Do it, and imagine deleting it from the graph. Some other tasks may now have no unmet dependencies; their in-degree has dropped to 0. Repeat.

  1. Compute the in-degree of every vertex.
  2. Put all vertices with in-degree 0 into a queue.
  3. Take a vertex from the queue and append it to the answer. For each outgoing edge v -> w, decrease the in-degree of w. If it becomes 0, enqueue w.
  4. When the queue is empty, you are done. If the answer holds fewer than V vertices, the rest are stuck behind a cycle.
Python Kahn's algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A trace

Follow the in-degrees on the morning graph. Start: wake 0, shower 1, coffee 1, dress 1, breakfast 1, leave 2.

TEXT
queue: [wake]                           order: []
take wake      -> shower 0, coffee 0    queue: [shower, coffee]
take shower    -> dress 0               queue: [coffee, dress]
take coffee    -> breakfast 0           queue: [dress, breakfast]
take dress     -> leave 1               queue: [breakfast]
take breakfast -> leave 0               queue: [leave]
take leave                              order: wake shower coffee dress breakfast leave

Every vertex enters the queue once and every edge is examined once, so Kahn's algorithm runs in O(V + E) time with O(V) extra space.

Kahn's algorithm doubles as a cycle detector. When the graph has a cycle, the vertices on it (and everything that depends on them) never reach in-degree 0, so len(order) < V. The output above shows how the second call fails.

DFS-based topological sort

A depth-first search gives a second approach. When DFS finishes a vertex, every vertex reachable from it, everything that must come after it, is already finished. So if you write vertices down in order of finishing, you get the reverse of what you want. Reverse that list and you have a topological order.

TEXT
finish order:   leave, dress, shower, breakfast, coffee, wake
reversed:       wake, coffee, breakfast, shower, dress, leave   <- valid
Python Topological sort with DFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both algorithms are correct; they just return different valid orders. Kahn's version is iterative, so it cannot run out of recursion depth, and it detects cycles naturally. The DFS version is short and fits well when you already have DFS machinery.

Problem: Course Schedule

You must take n courses numbered 0 to n - 1. A pair [a, b] means "to take course a, you must first take course b". Can you finish all courses? Return a valid order, or an empty list if it is impossible.

The pairs are edges b -> a. A valid plan exists exactly when the graph is a DAG, and a topological order is a valid plan.

A brute force would try every ordering of the courses, which is n! possibilities. The topological sort does it in O(n + m) for m prerequisite pairs.

Python Course schedule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Longest path in a DAG: the critical path

In a general graph, finding the longest path is very hard. In a DAG it is easy, because a topological order lets you process each vertex after all vertices that feed into it. This is dynamic programming on a graph.

Suppose each task takes some number of days and tasks can run in parallel when they do not depend on each other. The earliest a task can finish is its own duration plus the latest finish time among its prerequisites. The largest finish time of any task is the length of the critical path: the minimum time for the whole project.

Python Critical path of a project

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The longest chain is design (3), backend (5), tests (2), launch (1), which is 11 days. The frontend work fits inside the backend work's time, so speeding it up would not shorten the project. That is why project managers care about the critical path.

Built-in and variations

Python 3.9+ ships graphlib.TopologicalSorter in the standard library. You give it, for each node, the nodes it depends on (note: predecessors, the reverse of our adjacency lists), and it returns an order or raises CycleError.

Sometimes you need a particular order among the valid ones, for example the alphabetically smallest. Replace Kahn's queue with a min-heap: always take the smallest available vertex.

Python graphlib and the smallest valid order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The heap version costs O((V + E) log V) because of the heap operations.

All topological orders

Sometimes one valid order is not enough: you may need to list every one (to count schedules, or to test all interleavings of dependent jobs). Use backtracking on top of Kahn's idea. At each step, every vertex with in-degree 0 is a legal next choice. Try each one in turn: take it, lower the in-degree of its neighbors, recurse, then undo the change and try the next candidate.

Python Listing every topological order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the graph has a cycle, no vertex ever reaches in-degree 0 inside it, so the list stays empty. The number of orders can be as large as n! (a graph with no edges), so only do this for small inputs. Time is O(n ยท number of orders) in the worst case.

Common mistakes

  • Reversing the edges. "Course a needs b" is the edge b -> a. Draw one example before coding.
  • Forgetting disconnected parts. DFS must be started from every unvisited vertex; Kahn handles this automatically because every in-degree-0 vertex is seeded.
  • Not checking for a cycle. If you skip the len(order) == V test, a cyclic input silently returns a short list.
  • Assuming the order is unique. Tests should check validity (every edge goes forward), not equality with one particular answer, unless the problem fixes tie-breaking.
  • Forgetting graph[w] for sink nodes. Every vertex, including those with no outgoing edges, must be a key in your adjacency dict.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which graphs have a topological order?

    A cycle would require some vertex to come before itself. A topological order exists exactly for DAGs.
  2. 2. In Kahn's algorithm, how do you know that the graph has a cycle?

    Vertices on a cycle never reach in-degree 0, so they are never output. Fewer than V outputs means a cycle (an empty starting queue is just the extreme case).
  3. 3. In the DFS method, how is the topological order obtained?

    A vertex finishes after everything reachable from it. Reversing the finish order puts each vertex before all vertices it points to.
  4. 4. What is the time complexity of Kahn's algorithm on a graph with V vertices and E edges?

    Each vertex is enqueued and dequeued once and each edge decreases an in-degree once.
  5. 5. Tasks A, B, C, D take 2, 3, 4, 1 days. B and C both need A, and D needs B and C. Tasks may run in parallel. How long does the project take at least?

    The critical path is A (2) then C (4) then D (1), a total of 7 days. B runs in parallel with C and finishes earlier.

Summary

  • A topological order lists every vertex after all vertices that point to it; it exists only for DAGs and is usually not unique.
  • Kahn's algorithm repeatedly outputs vertices with in-degree 0 and lowers the in-degree of their successors. It runs in O(V + E) and detects cycles when fewer than V vertices are output.
  • The DFS method outputs vertices in reverse finishing order; it needs the same three-color cycle check.
  • Course schedule is "topological sort in disguise": prerequisites are edges, and an empty result means a cycle.
  • Processing a DAG in topological order solves longest-path (critical path) problems with simple dynamic programming.
  • Use a min-heap instead of a queue for the smallest valid order, or graphlib.TopologicalSorter for a ready-made solution.

Next: Bipartite Graphs and Coloring