Introduction to Topological Sort

Let’s go over the Topological Sort pattern, its real-world applications, and some problems we can solve with it.

About the pattern

Topological sorting is a technique used to organize a collection of items or tasks based on their dependencies. Imagine there is a list of tasks to complete, but some tasks can only be done after others are finished. There are many such tasks that depend on each other, or there’s a specific sequence of actions that must be followed. For example, when baking a cake, there are several steps one needs to follow, and some steps depend on others. We can’t frost the cake until it’s baked, and we can’t bake it until we’ve mixed the batter. To ensure that we don’t frost the cake before baking it or mix the batter after preheating the oven, we need to sort the steps based on their dependencies. This is where topological sorting helps us. It figures out the correct sequence of steps to bake the cake efficiently.

The topological sort pattern is used to find valid orderings of elements that have dependencies on or priority over each other. These elements can be represented as the nodes of a graph, so in technical terms, topological sort is a way of ordering the nodes of a directed graph such that for every directed edge [a,b][a,b] from node aa to node bb, aa comes before bb in the ordering.

Note: Topological sort is only applicable to directed acyclic graphs (DAGs), meaning there should be no cycles present in the graph.

If we write a recipe for baking a cake, then the list of tasks goes like first mix the batter, then bake the cake, and finally, frost it. These tasks can also be organized in a graph, where each task is a node, and the dependencies between tasks are represented by directed edges.

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy