A+DS

Topological Sort

Order tasks so dependencies come first.

Topological Sort produces a linear ordering of nodes in a directed acyclic graph (DAG) such that for every directed edge uā†’v, node u appears before v. It's essential for scheduling tasks with dependencies ā€” like course prerequisites or build systems.

  DAG:  A ā†’ C ā†’ F
         \        ā†‘
          D ā†’ G
         /
    B ā†’ E ā†’ G

  In-degrees: A=0 B=0 C=1 D=2 E=1 F=2 G=2
  Order: A, B, C, D, E, F, G

How it works

  1. 1Compute in-degree (number of incoming edges) for each node
  2. 2Enqueue all nodes with in-degree 0 (no dependencies)
  3. 3Dequeue a node, add it to the ordering, and decrement in-degrees of its neighbors
  4. 4When a neighbor's in-degree reaches 0, enqueue it

Loading...