Linearly ordering the vertices of a Directed Acyclic Graph (DAG).
Topological Sort is not a sorting algorithm in the traditional sense; rather, it's a linear ordering of the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge from vertex `u` to `v`, vertex `u` comes before vertex `v` in the ordering. If a graph contains a cycle, it is impossible to create a topological sort. This algorithm is fundamental in solving problems involving dependencies. For example, if you have a set of tasks where some tasks must be completed before others, a topological sort will give you a valid sequence in which to perform them. The most common algorithm for topological sorting is based on Depth-First Search (DFS). We perform a DFS traversal of the graph and keep track of the vertices in the order they finish their exploration (i.e., after all their descendants have been visited). The topological sort is then the reverse of this finishing order. Another popular approach is Kahn's algorithm, which is an iterative method that uses in-degrees of vertices. It starts by adding all vertices with an in-degree of 0 to a queue. Then, it repeatedly dequeues a vertex, adds it to the sorted list, and decrements the in-degree of all its neighbors. If a neighbor's in-degree becomes 0, it's added to the queue. This process continues until the queue is empty.