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
