Topological Sorting

Topological Sorting is a linear ordering of Vertices in a Directed Acyclic Graph (also known as DAG), such that for every directed edge $(u,v)$, vertex $u$ appears before $v$ [1]. There might be more than one orders. In fact, for the following graph:

We can have these three orders:

[a, b, c, d]
[a, c, b, d]
[a, c, d, b]

Usage

This sorting is widely used to schedule tasks, solve dependencies and plan course prerequisite.

The Kahn's algorithm can be used to implement such sorting. It uses in-degrees of vertices. The vertices with zero in-degrees are repeatedly removed and the corresponding neighbors' in-degrees are updated accordingly.

Example

The Course Schedule is a classic problem where we can apply Topological Sorting by using the Kahn's algorithm.

References

• [1]: https://en.wikipedia.org/wiki/Topological_sorting