One Pager Cheat Sheet

• The main objective of this lesson is to teach about Topological Sort and its use for programming interviews and challenges.
• A topological sort is a sorting technique used to linearly arrange the nodes in an acyclic, directed graph or tree based on the order the edges point.
• Topological sorting is an ordered approach to visiting the vertices of a Directed Acyclic Graph that follows the direction of its edges.
• A DAG (Directed Acyclic Graph) has no cycles so it can be used for Topological Sorting, allowing for the linear ordering of its vertices.
• By following a specific order of visiting nodes with no incoming edges and consecutively marking them as visited/finished, we can topologically sort a given graph.
• To arrange the nodes linearly in a descending order of their finished time steps is called Topological Sort, which is best used for scheduling tasks or specifying preconditions for a specific task.
• This topological sort can be implemented using Python.
• The output of the script is presented below.