Understanding topological sort

A graph can be used to model various problems involving relationships between entities and solve them efficiently. Often, when modelling problems using a graph, we end up with a directed graph that does not contain any cycles (a directed acyclic graph). Since these graphs are directed and don't have any cycles, we can define a linear ordering of their nodes such that each node appears before all the other nodes connected to it directly or indirectly via out-edges. Such an ordering is called the topological sort or topological ordering of the graph.

Let's look at a few examples to better understand the types of problems that are modelled using a directed-acyclic graph and what the topological ordering for them represents.