Identify

problem will deal with graphs that have no directed cycles
if you’re asked to update all objects in a sorted order
if you have a class of objects that follow a particular order
Topological Sort pattern is very useful for finding a linear ordering of elements that have dependencies on each other.
scheduling or grouping problems that have dependencies between items are good examples to problems that can be solved by using this technique

Motive

Topological Sort is used to find a linear ordering of elements that have dependencies on each other
- for example, if event ‘B’ is dependent on event ‘A’, ‘A’ comes before ‘B’ in topological ordering
this pattern defines an easy way to understand the technique for performing topological sorting of a set of elements

initialization a) store the graph in adjacency lists by using a HashMap b) to find all sources, use a HashMap to keep the count of indegreesBuild the graph and find in-degrees of all vertices
build the graph from the input and populate the in-degrees HashMap.
find all sources a) all vertices with ‘0’ in-degrees will be sources and are stored in a Queue
sort a) for each source, do the following things: i) add it to the sorted list ii) get all of its children from the graph iii) decrement the in-degree of each child by 1. iv) if a child’s in-degree becomes ‘0’, add it to the sources Queue b) repeat (a), until the source Queue is empty

where v is the total number of courses and e is the total number of prerequisites.

since we are storing all of the prerequisites for each course in an adjacency list.