DSA Notes

Graphs

Topological Sort

Order the vertices so that every edge points forward.

The idea

A topological order lists the vertices of a directed graph so that for every edge u → v, u comes before v. It exists exactly when the graph has no cycle (a DAG).

Kahn’s algorithm: count incoming edges for every vertex, repeatedly take a vertex with none, and remove its outgoing edges. If fewer than n vertices come out, there is a cycle.

Processing vertices in topological order is how dynamic programming runs on a DAG, for example the longest path.

Sample problem

210. Course Schedule II ↗ Medium

There are n courses. A pair [a, b] means course b must be taken before course a. Return an order in which all courses can be taken, or an empty list if it is impossible.

numCourses = 5, prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3]]
output = [0,1,2,3,4]

Why the solution works

The courses and prerequisites form a directed graph, and a valid order is a topological order: every edge points forward.

A course with no unfinished prerequisite is always safe to take next. Taking it removes its outgoing edges, which may free other courses. Kahn’s algorithm repeats this with a queue.

If the prerequisites contain a cycle, the courses on it wait for each other forever, the queue runs dry early, and fewer than n courses are output. That is how impossibility is detected.

Complexity: O(V + E) time and memory.

Watch out

  • Detect cycles by comparing the size of the order with n.
  • Many orders can be valid; if the problem wants the smallest one, use a priority queue instead of a queue.
  • For DP on a DAG, relax edges in this order so every source value is final when used.
Watch it run

Practise on LeetCode