LESSON 100 · ALGORITHMS34 min

Schedule Dependent Tasks with Topological Sort

Return tasks in an order that places every prerequisite before its dependent task.

Before you start: Dictionaries · Tuples and Sets · Functions · Build Queues and Stacks with deque

Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons

WATCH

Video lesson: Schedule Dependent Tasks with Topological Sort

The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube

Jump to a chapter

Read the video transcript

Select a timestamp to watch that moment on YouTube.

00:00
Many tasks have dependencies. A package must be built before it can be tested, and a deployment should happen after the tests. Alphabetical order does not encode those rules. A topological sort takes a directed dependency graph and produces an order in which every prerequisite comes before the task that needs it. Today we will first run a wrong alphabetical schedule, then count how many unmet prerequisites each task has. We will implement a small form of Kahn's algorithm using a heap so tasks that are equally ready come out in a predictable order. Finally, we will give the algorithm a cycle and verify that it reports the
00:40
impossible schedule instead of silently returning a partial list. These examples are about local strings and dictionaries, not a cloud deployment system. The point is to see why an order is valid. A valid topological order is not always unique; unrelated tasks can appear in either order. Deterministic tie-breaking helps tests and reports stay stable, but it does not create a dependency where none exists. Sorting gives us a stable list, but stable does not mean valid. `deploy` appears before `test`, even though the dependency map says deployment requires testing. The Boolean check is False, demonstrating the violation.
01:22
If a script used this order to execute real jobs, it could deploy code that was never tested. A common workaround is to assign a manual number to each task. That can work for one fixed workflow, but adding another dependency requires revisiting the numbering, and cycles can remain hidden. The graph itself should determine which tasks are ready. We need to start with tasks that have no prerequisites, remove each completed task from the remaining dependency counts, and continue as newly ready tasks appear. If no task is ready but unfinished tasks remain, we have a cycle or an invalid dependency reference.
02:03
The next run will inspect the initial counts and the connections needed to update them. `indegree` is the number of prerequisites still outstanding for each task. At the beginning, build has zero, while test and deploy each wait for one earlier task. The `dependents` mapping runs in the other direction: when build finishes, which tasks should have their counts reduced? Test is one; when test finishes, deploy becomes ready. Keeping both views makes the algorithm efficient and understandable. The graph in this example is small, but the same pattern applies to package builds, spreadsheet formulas, and prerequisite lessons. We also need to reject references to tasks that do not exist.
02:47
Otherwise a typo could leave a task blocked forever and look like a cycle. The implementation in the next chapter checks that condition explicitly. We will use a min-heap of ready task names to choose a repeatable order among tasks with zero outstanding dependencies. That choice affects presentation, not correctness of the dependency rule. The heap starts with every task that has zero outstanding prerequisites. We take one ready task, append it to the result, then reduce the counts of tasks that depended on it. A dependent enters the heap only when its count reaches zero, meaning all of its prerequisites have already appeared in the result.
03:29
For this graph, build unlocks test, and test unlocks deploy. The final length check catches a cycle: if some tasks remain but none can become ready, the algorithm cannot produce a full order. Before doing any work, we also check for unknown prerequisites to distinguish a misspelled task from a genuine cycle. The heap gives an alphabetical tie-break among unrelated ready tasks, which helps the same graph produce the same displayed order. Other tie-break policies are possible, and a task scheduler might use priority or duration instead. The correctness requirement remains the same: no task appears before any prerequisite listed for it.
04:11
Lint and build are initially independent, so either could run first without violating the graph. We assert the relationships that matter instead of requiring one arbitrary full order. Test follows build, and deployment follows both test and lint. The heap happens to make the displayed order repeatable by task name. The second graph says a needs b and b needs a. Neither can start, so the algorithm raises an error rather than returning an empty list as though no work existed. This check is essential in a build pipeline: a partial plan can look plausible while silently omitting blocked tasks. Try adding a task that depends on a name missing from the graph and compare the
04:55
full validator from the previous chapter, which reports an unknown prerequisite, with this shorter verification helper. On the page, complete the task by producing an order and adding one negative test. The lesson's durable idea is that prerequisites determine readiness, not spelling or the order keys happen to appear in a dictionary.

THE IDEA

Understand the concept

Some tasks cannot start until other tasks finish. A build must precede tests, and tests must precede deployment. Alphabetical sorting ignores those dependencies. A topological sort produces an order where each prerequisite appears first. It exists only for a directed acyclic graph: a cycle such as build needing test while test needs build makes the plan impossible.

Represent the graph as a dictionary whose keys are task names and whose values are sets or lists of prerequisite names. Validate that every prerequisite has its own key; silently inventing a missing task can hide a typo. An indegree count tracks how many prerequisites each task still has, while a reverse adjacency map records which tasks become closer to ready when one task is completed.

Kahn's algorithm starts with all zero-indegree tasks. Pop one ready task, append it to the result, decrement each dependent's count, and add dependents that reach zero. This lesson uses heapq for the ready queue so independent tasks have stable alphabetical tie-breaking, regardless of dictionary insertion order. The tie-breaker is a presentation choice; the dependency constraint is what makes the result correct.

If the result has fewer tasks than the input, a cycle remains. Raise ValueError rather than returning a misleading partial schedule. The checked function also rejects an unknown prerequisite and an empty or non-string task name. Tests include a straight chain, independent tasks, a shared prerequisite, and a cycle. For very large graphs, recursion-based depth-first code can hit a recursion limit; this iterative algorithm avoids that issue.

Dependencies form a directed graph
Zero-indegree tasks are ready
A heap gives deterministic ties
Unprocessed nodes reveal a cycle

WORKED EXAMPLES

See it step by step

Read the code, predict the output, then compare it with the result.

01. See why alphabetical order fails

PYTHON

plan = {'deploy':['test'], 'test':['build'], 'build':[]}
print(sorted(plan))
print(sorted(plan) == ['build','test','deploy'])

EXPECTED OUTPUT

['build', 'deploy', 'test']
False

Alphabetical order can put deployment before its test prerequisite.

02. Count prerequisites

PYTHON

plan = {'deploy':['test'], 'test':['build'], 'build':[]}
print({task: len(needs) for task, needs in plan.items()})
print(sorted(task for task, needs in plan.items() if not needs))

EXPECTED OUTPUT

{'deploy': 1, 'test': 1, 'build': 0}
['build']

Only build is initially ready; completing it releases test.

03. Identify a cycle

PYTHON

plan = {'a':['b'], 'b':['a']}
print([task for task, needs in plan.items() if not needs])
print(len(plan))

EXPECTED OUTPUT

[]
2

No task can start, so a valid complete order cannot exist.

GO DEEPER

A closer look

Follow the reasoning, inspect each result, then try the suggested changes in the console below.

01 / 03

Expose the failure of alphabetical ordering

In the first plan, deploy needs test and test needs build. Sorting the task names alphabetically puts deploy before test, which violates the dependency rule even though the names are in a perfectly deterministic order. A label-based sort cannot infer which tasks must happen first.

Represent each task with its prerequisite names and validate that every referenced prerequisite is present. The algorithm must return a sequence in which each prerequisite appears before the task that needs it. Several sequences may satisfy the rule; an alphabetical tie breaker among simultaneously ready tasks only makes the result predictable for readers and tests.

PYTHON

plan = {'deploy':['test'], 'test':['build'], 'build':[]}
print(sorted(plan))
print(sorted(plan) == ['build','test','deploy'])

EXPECTED OUTPUT

['build', 'deploy', 'test']
False

Follow the reasoning

Write down the prerequisite chain.
Compare alphabetical order with dependency order.
Validate references before scheduling any task.

02 / 03

Start with tasks that need nothing

The second run counts prerequisites for each task and finds build as the only initially ready entry. Once build is completed, test can become ready; only after test is completed can deploy become ready. That progression is the core of Kahn's topological sorting algorithm.

Track a count of unmet prerequisites and a reverse mapping from each task to its dependents. Put zero-count tasks into a ready queue. For stable output when several are ready, use a heap or another deliberate tie breaker rather than relying on dictionary insertion order. After removing one task, decrement only its dependents and enqueue those that reach zero.

PYTHON

plan = {'deploy':['test'], 'test':['build'], 'build':[]}
print({task: len(needs) for task, needs in plan.items()})
print(sorted(task for task, needs in plan.items() if not needs))

EXPECTED OUTPUT

{'deploy': 1, 'test': 1, 'build': 0}
['build']

Follow the reasoning

Count incoming prerequisites for every task.
Seed the ready queue with zero-count tasks.
Release dependents only when their count reaches zero.

03 / 03

Detect when a cycle prevents completion

The final example has a needing b and b needing a. No task is initially ready, while the plan still contains two tasks. Returning an empty list as though it were a valid schedule would hide the impossible dependency structure. A complete topological order cannot exist for this cycle.

After the queue is exhausted, compare the output length with the input task count. If fewer tasks were emitted, raise ValueError and ask the caller to repair the graph. Also reject unknown prerequisite names before the algorithm begins. Tests should include a chain, independent tasks, shared dependencies, and a cycle so the behavior is clear.

PYTHON

plan = {'a':['b'], 'b':['a']}
print([task for task, needs in plan.items() if not needs])
print(len(plan))

EXPECTED OUTPUT

[]
2

Follow the reasoning

Observe that the initial ready set is empty.
Compare emitted task count with the input graph.
Raise on cycles instead of returning a partial plan.

HANDS-ON

Try it in Python

Edit the example and run it. Python starts in your browser the first time you click Run.

Python console

Ready to run

def task_order(dependencies):
    return sorted(dependencies)

plan = {'deploy': ['test'], 'test': ['build'], 'build': []}
print(task_order(plan))

Need input()? Add one value per line

Input lines

Ctrl / ⌘ + Enter to run

OUTPUT

Your output appears here.

Your turnComplete task_order(dependencies). Require nonblank string task names and known prerequisite names; use a deterministic topological sort with alphabetical tie-breaking. Raise ValueError for unknown prerequisites or cycles. Prepared output must be ['build', 'test', 'deploy'].

Need a hint?

Count prerequisites, make a reverse map, heapify zero-count tasks, and decrement dependents as each task leaves the heap. A shorter final order means a cycle.

Complete the task and select Check task to verify your code.

DEBUG BETTER

Typical mistakes

Everyone meets these errors. See what causes them and how to fix them.

Alphabetical sorting of task names

COMMON MISTAKE

return sorted(dependencies)

FIX

ready = [name for name, needs in dependencies.items() if not needs]
# Release dependents only after their prerequisites.

What happens: deploy can appear before test.
Use graph relationships, not labels, to establish order.

Returning a partial order on a cycle

COMMON MISTAKE

return order  # even if some tasks remain

FIX

if len(order) != len(dependencies):
    raise ValueError('dependency cycle')

What happens: The plan omits work without explaining why.
A cycle means no complete valid ordering exists.

Browse this lesson’s problem fixes

VERIFY THE STORY

Sources and further reading

Python heapq documentation