Skip to main content
Code ScholarsCodeScholars

Graphs and Network Algorithms · Graph Algorithms

Topological Sort

Topological sort orders directed acyclic graph vertices so every prerequisite appears before the thing that depends on it.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

Students use dependency examples before moving into code.

Guided Lesson Notes

Understanding Topological Sort

Topological Sort focuses on relationships, reachability, paths, cycles, connectivity, and optimization over edges. Topological sort orders directed acyclic graph vertices so every prerequisite appears before the thing that depends on it.

Model: draw vertices as dots and edges as connections; then decide whether direction, weight, or capacity matters.

Invariant: visited, distance, parent, component, or flow arrays must match what has actually been discovered so far.

Implementation: adjacency lists or matrices, queues, stacks, priority queues, union-find, and repeated edge relaxation.

Use Topological Sort when the problem mentions roads, networks, prerequisites, components, shortest paths, spanning costs, or dependency order.

Visual Model

A small picture for Topological Sort

ABCDE

Key Ideas

  • DAG requirement
  • In-degree method
  • DFS finishing-order method

Practice Prompts

  • Order course prerequisites with topological sort.
  • Detect why a cycle prevents a valid ordering.

Vocabulary

Terms students should be able to say clearly

Vertex

An object or state in the graph.

Edge

A relationship or move between vertices.

Path

A sequence of edges from one vertex to another.

Cycle

A path that returns to a previous vertex.

Component

A group of vertices connected by reachability.

Relaxation

Trying to improve a known distance or cost through an edge.

Worked Example

Worked example: tracing Topological Sort

Trace a small input, focusing on dag requirement.

  1. 1Write a small input where Topological Sort is clearly useful.
  2. 2Label the part of the input related to DAG requirement.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Adjacency-list traversalO(V + E)DFS and BFS visit vertices and inspect edges.
Adjacency matrix storageO(V^2)A matrix reserves space for every possible pair.
Weighted optimizationVariesMST and shortest-path algorithms depend on sorting, heaps, and graph density.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Topological Sort interview problem: Course Schedule Order

Interview medium

Problem

Given course prerequisites, print an order in which all courses can be taken, or report that it is impossible.

Input

The first line contains n and m. Each of the next m lines contains course prerequisite, meaning prerequisite must come first.

Output

Print one valid order of courses, or IMPOSSIBLE if a cycle exists.

Sample Input

4 4
1 0
2 0
3 1
3 2

Sample Output

0 1 2 3

Why the sample works

Course 0 unlocks courses 1 and 2, and both are needed before course 3.

Approach

  1. 1Build the graph from prerequisite to course.
  2. 2Track indegrees for every course.
  3. 3Repeatedly process courses with indegree 0.
  4. 4If fewer than n courses are processed, a cycle blocks completion.

O(n + m) time and O(n + m) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();

    List<Integer>[] graph = new ArrayList[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    int[] indegree = new int[n];

    for (int i = 0; i < m; i++) {
      int course = sc.nextInt();
      int prereq = sc.nextInt();
      graph[prereq].add(course);
      indegree[course]++;
    }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
      if (indegree[i] == 0) q.add(i);
    }

    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
      int node = q.remove();
      order.add(node);
      for (int next : graph[node]) {
        indegree[next]--;
        if (indegree[next] == 0) q.add(next);
      }
    }

    if (order.size() != n) {
      System.out.println("IMPOSSIBLE");
    } else {
      for (int i = 0; i < order.size(); i++) {
        if (i > 0) System.out.print(" ");
        System.out.print(order.get(i));
      }
      System.out.println();
    }
  }
}

Python Solution

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
indegree = [0] * n

for _ in range(m):
    course, prereq = map(int, input().split())
    graph[prereq].append(course)
    indegree[course] += 1

q = deque(i for i in range(n) if indegree[i] == 0)
order = []

while q:
    node = q.popleft()
    order.append(node)
    for nxt in graph[node]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            q.append(nxt)

print("IMPOSSIBLE" if len(order) != n else " ".join(map(str, order)))

Practice Challenge

Make the idea your own

Create a two-minute explanation of Topological Sort: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler