Ravindra Ranwala's Blog

This article shows how we can use depth-first search to perform a topological sort of a directed acyclic graph, or a “dag” as it is sometimes called. A topological sort of a dag $G = (V, E)$ is a linear ordering of all its vertices such that if $G$ contains an edge $(u, v)$, then $u$ appears before $v$ in the ordering. (If the graph contains a cycle, then no linear ordering is possible.) We can view a topological sort of a graph as an ordering of its vertices along a horizontal line so that all directed edges go from left to right. Topological sorting is thus different from the usual kind of “sorting”. [1] The following simple algorithm topologically sorts a dag: Now let’s take a look at a real world application of the Topological sort algorithm. Course Schedule There are a total of $n$ courses you have to take, labeled from $0$ to $n-1$. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: $\left[ \b...