Topological Sorting in Directed Acyclic Graph

Topological Sorting is a graph ordering technique for Directed Acyclic Graphs (DAGs). Learn topological sort using DFS and Kahn’s algorithm, with examples, complexity, advantages, and applications.

Topological Sorting in Directed Acyclic Graph

Introduction

Topological Sorting is a graph ordering technique used for Directed Acyclic Graphs (DAGs).

In topological sorting, the vertices of a directed graph are arranged such that for every directed edge

u→v

vertex u appears before v in the ordering.

Topological sorting is possible only for directed graphs that do not contain cycles.

Need for Topological Sorting

Topological sorting is used in:

• Task / job scheduling
• Course prerequisite problems
• Program compilation order
• Dependency resolution in software systems

Conditions for Topological Sorting

• The graph must be directed
• The graph must be acyclic (i.e., a DAG)

Methods of Topological Sorting

Two main methods are used:

1. DFS-based method
2. Kahn’s Algorithm (BFS-based method)

Topological Sorting Using DFS

In the DFS-based method:

• Perform DFS traversal of the graph
• After all adjacent vertices of a vertex are processed, push the vertex onto a stack
• When all vertices are processed, pop vertices from the stack to obtain the topological order

Algorithm: Topological Sorting Using DFS

TopologicalSort(G)

create empty stack S

mark all vertices as unvisited

for each vertex v in G

if v is not visited

DFS(v)

DFS(v)

mark v as visited

for each vertex u adjacent to v

if u is not visited

DFS(u)

push v into stack S

print vertices by popping stack S

Example

Consider the following dependencies:

• A → C
• B → C
• C → D

One possible Topological Order is:

A,B,C,D

(Note: More than one valid topological order may exist.)

Time and Space Complexity

• Time Complexity: O(V+E)
• Space Complexity: O(V)

Where:

• V = number of vertices
• E = number of edges

Advantages and Limitations of Topological Sorting

Advantages:

• Makes dependencies clear
• Useful for solving scheduling problems
• Helps in build and execution order

Limitations:

• Not possible for graphs with cycles
• Not applicable to undirected graphs

Conclusion

Topological Sorting is an essential technique for Directed Acyclic Graphs (DAGs).
The correct ordering of vertices can be obtained using DFS-based or BFS-based (Kahn’s) algorithms.
It is widely used for solving dependency-based problems in computer science.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1