**Topological sorting** is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.

A **Directed Acyclic Graph (DAG)** is a graph that is directed, meaning that edges have a direction, and it is acyclic, meaning that there are no cycles or closed loops in the graph.

â€¢ In concurrent systems, topological sorting can be used to avoid deadlocks by ensuring that resources are acquired in a safe order.

**Note**: Topological sorting is applicable only to directed acyclic graphs (DAGs). It cannot be used on graphs with cycles.

## Steps for Topological Sorting:

- Identify vertices with in-degree 0 (vertices with no incoming edges).
- Select a vertex with in-degree 0.
- Remove the selected vertex and its outgoing edges.
- Repeat steps 1-3 until all vertices are included.
- If at any point there are no vertices with in-degree 0, and the graph is not empty, the graph contains a cycle (not a DAG).

## Applications of Topological Sorting:

Some of the applications of topological sorting are listed below:

- Task Scheduling
- Build Systems
- Network Dependency Analysis
- Task Execution Order