Topological sorting is a fundamental concept in graph theory used to order tasks based on dependencies in a directed acyclic graph (DAG). It is widely used in scheduling, project planning, and dependency resolution in computer science.
What is Topological Sort?
Topological sort is a linear ordering of vertices in a directed graph such that for every directed edge (u → v), vertex u appears before v in the ordering. The list of key concepts and working ideas of topological sorting is given below.
Directed Graph Requirement: Works only on directed graphs.
Acyclic Condition: Graph must not contain cycles.
Dependency-Based Ordering: Ensures prerequisites are processed first.
Multiple Valid Orders: A graph can have more than one valid topological sort.
Used in Real Applications: Task scheduling, course prerequisite systems, build systems.
Key Algorithms for Topological Sorting
Topological sorting can be performed using different algorithms depending on the approach. The list of major algorithms is given below.
1. Kahn’s Algorithm (BFS-Based)
Kahn’s algorithm uses Breadth-First Search and works by removing nodes with zero in-degree step by step.
In-Degree Calculation: Count incoming edges for each node.
Queue Initialization: Add nodes with zero in-degree.
Processing Nodes: Remove node and update neighbors.
Repeat Until Empty: Continue until all nodes are processed.
Cycle Detection: If nodes remain, graph contains a cycle.
2. DFS-Based Topological Sort
This method uses Depth-First Search and stack to generate ordering.
Visit Nodes Recursively: Traverse deeply before backtracking.
Push to Stack: After visiting all neighbors.
Reverse Stack Order: Gives topological sorting.
Efficient for Deep Graphs: Works well for recursive structures.
Cycle Handling: Requires visited tracking.
Topological Sort Examples with Algorithm Identification
Let’s explain some examples of topological sorting
Example 1: Simple DAG (Kahn’s Algorithm – BFS Based)
This example demonstrates topological sorting using Kahn’s algorithm, where nodes with zero in-degree are processed first, and the list of steps is given below.
Graph:
A → C
B → C
Why Kahn’s Algorithm?
Nodes A and B have in-degree = 0
They are added to a queue and processed first
Topological Orders:
A, B, C
B, A, C
Key Concept:
BFS-based approach naturally handles nodes with no dependencies first
Example 2: Task Scheduling (Kahn’s Algorithm – BFS Based)
This example is best suited for Kahn’s algorithm because it directly models dependency resolution using in-degree, and the list of explanation points is given below.
Tasks:
1 → 3
2 → 3
3 → 4
Why Kahn’s Algorithm?
Tasks 1 and 2 have no prerequisites (in-degree = 0)
Queue-based processing ensures correct scheduling
Topological Orders:
1, 2, 3, 4
2, 1, 3, 4
Key Concept:
Widely used in real-world scheduling systems
Example 3: Course Prerequisites (DFS-Based Algorithm)
This example fits well with DFS because it follows a deep dependency chain, and the list of explanation points is given below.
Courses:
Math → Programming
Programming → Data Structures
Data Structures → Algorithms
Why DFS Algorithm?
DFS explores one path completely:
Math → Programming → Data Structures → Algorithms
Nodes are pushed to stack after visiting dependencies
Topological Order:
Math → Programming → Data Structures → Algorithms
Key Concept:
DFS is ideal for chain-like dependencies
Example 4: Complex DAG (DFS-Based Algorithm)
This example uses DFS to handle multiple dependency chains efficiently, and the list of explanation points is given below.
Graph:
A → D
B → D
C → E
D → F
E → F
Why DFS Algorithm?
DFS explores each branch:
A → D → F
B → D → F
C → E → F
Stack helps maintain correct ordering
Topological Orders:
A, B, C, D, E, F
B, A, C, D, E, F
Key Concept:
DFS handles multiple paths and merging nodes
Example 5: Build System Dependencies (Both Algorithms Applicable)
This example can be solved using both Kahn’s and DFS algorithms, and the explanation is given below.
Dependencies:
Header → Source
Source → Object
Object → Executable
Why Both Algorithms?
Simple linear dependency chain:
Kahn’s: processes from start (Header)
DFS: explores full chain then reverses
Topological Order:
Header → Source → Object → Executable
Key Concept:
Linear graphs work efficiently with both approaches
Summary Table: Examples vs Algorithms
Example
Algorithm Used
Reason
Simple DAG
Kahn’s (BFS)
Multiple zero in-degree nodes
Task Scheduling
Kahn’s (BFS)
Real-world dependency scheduling
Course Prerequisites
DFS
Deep dependency chain
Complex DAG
DFS
Multiple paths and merging
Build System
Both (Kahn’s & DFS)
Linear dependency
Final Insight
Kahn’s Algorithm (BFS) is best when:
You want to track in-degrees
You need cycle detection easily
Real-world scheduling problems
DFS-Based Algorithm is best when:
You want recursive traversal
Graph has deep chains or multiple paths
You prefer stack-based ordering
Step-by-Step Topological Sort Example (Kahn’s Algorithm)
Topological Sort examples provide the linear ordering of the vertices. According to topological sort, if there is an edge in the diagram going from vertex ‘A’ to vertex ‘B’, then ‘A’ comes before ‘B’ in the ordering”.
Topological Sorting can be applied if and only if the graph is a Directed Acyclic Graph.
For one directed acyclic graph, more than one ordering sequence may exist.
Keep in mind that a directed Acyclic Graph is a graph having no graph cycles and is labeled with directed arrows.
Steps to Find the Topological Ordering
First, find the vertex which having the least in-degree.
Second, remove the least in-degree vertex along with its associated edges
Update the in-degree of the rest of the vertices.
Interlink all the removing (least in-degree) vertices in the order as they are removed from the directed acyclic graph.
In-degree:In-degree of a vertex is the number of edges coming into that vertex
Problem: Find all possible topological orderings for the given directed acyclic graph
Solution:
Step-01: Write in-degree of each vertex
Step-02: As vertex-A holds the least in-degree, remove it along with its associated edges and update the rest of the graph
Step-03:As vertex-B holds the least in-degree, remove it with its associated edges and update the rest of the graph
Step-04: There are two vertices with the similar least in-degree. So, there are two possible cases.
Case-01
Remove vertex-C before vertex-D
Case 02
Remove vertex-D before vertex-C
Above, both cases are valid, as given under
Step-05:Now, the above two cases will run separately parallel.
In case 01:
As vertex-D holds the least in-degree, remove it with its associated edges
The Last vertex-E is separated already by separating the second-last vertex-D.
In case-02:
As vertex-C holds the least in-degree, remove it with its associated edges
Step 06: As the Last vertex-E is separated already by separating the second-last vertex-C. So attach E to the last part of the ongoing ordering.
Result:
For the given directed acyclic graph, the following two different topological orderings are possible.
A→B→C→D→E
A→B→D→C→E
Applications of Topological Sort
Topological sorting is widely used in different real-world scenarios. The list of major applications is given below.
1. Task Scheduling Systems
Used in project management tools.
Ensures tasks are completed in order.
2. Course Scheduling
Determines correct order of courses.
Avoids prerequisite conflicts.
3. Build Systems
Used in compilers like Makefile.
Ensures correct file compilation order.
4. Dependency Resolution
Used in package managers.
Resolves library dependencies.
5. Workflow Management
Used in automation systems.
Ensures proper execution flow.
Advantages of Topological Sorting
Topological sorting provides several benefits in solving dependency-based problems. The list of advantages is given below.
Efficient Ordering: Ensures correct sequence of operations.
Multiple Solutions: Offers flexibility in ordering.
Wide Applicability: Used in many computing domains.
Limitations of Topological Sort
Despite its usefulness, topological sorting has some limitations. The list of challenges is given below.
Only for DAGs: Cannot be applied to cyclic graphs.
Cycle Detection Needed: Must handle cycles separately.
Multiple Outputs: May create ambiguity.
Graph Complexity: Large graphs can be harder to visualize.
Conclusion
Topological sort is a powerful technique for ordering tasks based on dependencies in a directed acyclic graph. By understanding examples and algorithms like Kahn’s and DFS, students can easily apply this concept in real-world problems such as scheduling, course planning, and software development systems.
