Suggest an editImprove this articleRefine the answer for “What is topological sorting? For which graphs is it possible?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**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. **Key point:** topological sorting is possible only for acyclic directed graphs (DAGs).Shown above the full answer for quick recall.Answer (EN)Image**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: ```javascript A → B → C A → D ``` 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".For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.