What is topological sorting? For which graphs is it possible?

Topological sorting is an ordering of the vertices of a directed graph in which every edge goes only from an earlier vertex to a later one.

In other words: If there is an edge u → v, then in the topological sort order u comes before v.

---

#When it's possible

Topological sorting is possible only for acyclic directed graphs (DAG - Directed Acyclic Graph). If the graph has a cycle, it is impossible to order the vertices without violating the direction of the edges.

---

#Example

Suppose a graph shows dependencies between tasks:

One possible order is: A, D, B, C (A first, because the others depend on it.)

---

#How it works (idea)

1. Find vertices with no incoming edges, they can go first.
2. Remove them from the graph along with their outgoing edges.
3. Repeat until all vertices are removed.

(This is how, for example, Kahn's algorithm or DFS-based sorting works.)

---

#Applications

• Scheduling tasks with dependencies (for example, code compilation).
• Determining the order of steps (construction, projects).
• Analyzing dependencies between modules, courses, events.

---

Summary: Topological sorting is a linear order of the vertices of a DAG, reflecting the dependency: "if A leads to B, then A must come before B".