Topological Sort

1:The topological sort algorithm takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to.

The ordering of the nodes in the array is called a topological ordering.

Well, let’s focus on the first node in the topological ordering. That node can’t have any incoming directed edges; it must have an indegree ↴ of zero. Then follow below algorithm.

This is a common algorithm design pattern:

1. Figure out how to get the first thing.
2. Remove the first thing from the problem.
3. Repeat.

Implementation

We’ll use the strategy we outlined above:

1. Identify a node with no incoming edges.
2. Add that node to the ordering.
3. Remove it from the graph.
4. Repeat.