Faangprep Logo
Log inStart free
Browse curriculum

Topological Sort

A topological sort is a linear ordering of the vertices of a directed acyclic graph (DAG) in which, for every directed edge u -> v, vertex u comes before v.

IN-DEGREES

Queue (in-degree 0)

A

Sorted order

Nothing emitted yet

 

Count each node's prerequisites. A has none, so it can go first.

Next

A has no unmet prerequisite. Emit it — position 1.

Algorithm

Intuition

Imagine you are getting dressed. You must put on socks before shoes, and underwear before pants.

You can't put on shoes first, then socks. Some tasks have dependencies.

Topological Sort gives you a valid order to perform tasks so that all dependencies are met.

Concept

Topological sorting puts the vertices of a directed graph in an order where every edge points forward: for an edge u -> v, u appears somewhere before v. Picture a valid order in which to take courses when some are prerequisites of others. Most graphs have more than one valid order.

It is only possible if the graph has no cycles (DAG).

How it Works

Kahn's Algorithm (BFS):
  1. Calculate in-degree (number of incoming edges) for each node.
  2. Add nodes with 0 in-degree to a Queue.
  3. Process Queue: remove node u, add to result.
  4. Decrease in-degree of neighbors. If a neighbor becomes 0, add to Queue.
  5. Repeat until Queue is empty.

Step-by-Step Breakdown

Watch the visualization:

  • Solid blue node: The node the current step acts on.
  • Pale blue node with a blue outline: Waiting: in Kahn's queue, or on the DFS stack.
  • Green node: Added to the sorted order.
  • Red node: On a cycle, so no topological order exists.
  • In-Degrees: In Kahn's mode, the number above a node is its count of unmet prerequisites.

When to Use

Use Topological Sort when:

  • Scheduling tasks with dependencies (e.g., project management, build systems).
  • Resolving symbol dependencies in linkers.
  • Course prerequisite planning.
  • Finding a cycle in a graph (if sort fails).

When NOT to Use

  • Cyclic Graphs: It's impossible to topologically sort a graph with a cycle.
  • Undirected Graphs: Only applies to directed graphs.

How to Identify

Problems about "ordering tasks", "prerequisites", "dependencies", or "build order" typically require Topological Sort.

Preparing for interviews? This topic is also taught as a pattern:

Ordering Dependencies (Topological Sort)

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Depth First Search

Next

Cycle Detection

Frequently Asked Questions

What is Topological Sort used for?

It is used for tasks with prerequisite hierarchies, such as course scheduling, build systems (Make), and package managers (npm).

Why must the graph be a DAG?

Cycles (Directed Cycles) create circular dependencies where no node can come "before" others, making linear ordering impossible.

Kahn's Algorithm vs DFS?

Kahn's uses In-degrees and a Queue. DFS uses a post-order traversal and a Stack. Both produce a valid topological ordering in O(V+E).