Topological Sort

DSA · Graphs

Theory

A topological sort orders the vertices of a directed acyclic graph (DAG) so that every edge goes from earlier to later in the order. Kahn's algorithm counts incoming edges (in-degree) for each vertex, starts with vertices that have none, and repeatedly removes them while decreasing their neighbours' in-degrees. If not every vertex is output, the graph has a cycle. It runs in O(V + E).

Why we use it

It produces a valid order for tasks that depend on each other.

When to use it

Use it for build systems, course prerequisites, data pipeline task ordering (Airflow DAGs), spreadsheet recalculation and package installation.

How it works

  1. Count in-degree of every node
  2. queue = nodes with in-degree 0
  3. Queue empty? Yes: Done. No: Pop u, add to order.
  4. For each edge u -> v: in-degree[v] -= 1; if 0 push v
  5. Order has all nodes? Yes: Valid order. No: Graph has a cycle.

Syntax

indeg = count incoming edges
queue = vertices with indeg 0
while queue:
    v = pop; output v
    for nb in graph[v]:
        indeg[nb] -= 1
        if indeg[nb] == 0: push nb
Time: O(V + E)

Example

from collections import deque

tasks = {
    "extract": ["clean"],
    "clean": ["join", "validate"],
    "validate": ["load"],
    "join": ["load"],
    "load": ["report"],
    "report": [],
}

indeg = {t: 0 for t in tasks}
for t in tasks:
    for nxt in tasks[t]:
        indeg[nxt] += 1

q = deque([t for t in tasks if indeg[t] == 0])
order = []
while q:
    t = q.popleft()
    order.append(t)
    for nxt in tasks[t]:
        indeg[nxt] -= 1
        if indeg[nxt] == 0:
            q.append(nxt)
print("Run order:", " -> ".join(order))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic