Application 1: Topological Sort

In this lesson, we’ll apply the DFS algorithm to solve a task ordering problem.

The topological sorting problem

Our goal is to order a set of tasks in a way that respects the dependencies between them. For example, let’s assume that you’re planning your activities for the day. Unfortunately, there is a collection of household chores that you’ll need to complete first, such as washing the dishes, withdrawing cash, grocery shopping, and cooking. Some of these activities may depend on each other. For instance, you need to shop for groceries before you can cook dinner. And you need to withdraw cash before you can shop for groceries.

These tasks and dependencies can be modeled in a task graph. Each task is a node of the graph, and there is an edge $(u, v)$ whenever task $v$ directly depends on task $u$. The following figure shows an example task graph.

Whenever there is a path $u \rightarrow v$ in the task graph, the task $v$ (directly or indirectly) depends on the task $u$. This means that we have to perform task $u$ before we can perform task $v$ ...