A topological sorting of nodes in a graph is an ordering of the nodes in the graph where every node appears only after all the nodes pointing to it have appeared.
For example, for a graph with 4 nodes and these relations:
c→d, there are two acceptable topological sorts:
a, b, c, d and
a, c, b, d.
Topological order of the nodes is defined only for directed acyclic graphs (DAGs). See below for the expected result for graphs with cycles.
Topological ordering of the nodes is beneficial when you want to guarantee a node will only be consumed after its dependencies were consumed.
Running the algorithm on a graph with cycles will cause the omitting of part of the nodes from the sorting. The omitted nodes are:
Nodes that are part of a cycle (including self cycles)
Nodes that are dependent on a cycle. It means nodes that are reachable from another node which is part of a cycle
All the other nodes in the graph will be ordered in a valid topological order.
Was this page helpful?