Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, node u comes before v in the order.

Key Points (Quick Revision)

• Works only on Directed Acyclic Graph (DAG)
• Maintains dependency order
• Uses DFS or Queue (Kahn’s Algorithm)
• Time Complexity: O(V + E)
• Used in scheduling problems

Topological Sort in Simple Words

Topological Sort means:

• Arrange tasks in a correct order
• So that dependency is followed

Real-Life Example

Think about:

• You must wear a shirt before a jacket
• You must complete the course before the exam
• You must cook before eating

This is dependency-based ordering, that is, Topological Sort.

Example Graph (DAG)

5 → 0 → 4
↓
2 → 3 → 1

Possible Topological Order:

5 → 2 → 3 → 1 → 0 → 4

When to Use Topological Sort

Use it when:

• Tasks depend on each other
• You need the correct execution order
• You are working with scheduling problems

Approach 1: DFS (Stack Method)

Steps:

1. Visit node
2. Go deeper using DFS
3. Push the node to the stack after visiting
4. Print stack

Approach 2: Kahn’s Algorithm (Queue Method)

Steps:

1. Calculate the in-degree of all nodes
2. Add nodes with in-degree = 0 to the queue
3. Remove node from queue
4. Reduce the in-degree of neighbors
5. Repeat

Java Code – Topological Sort (Kahn’s Algorithm)

import java.util.*;

public class TopologicalSort {

    int vertices;
    List<List<Integer>> graph;

    public TopologicalSort(int v) {
        vertices = v;
        graph = new ArrayList<>();

        for (int i = 0; i < v; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        graph.get(u).add(v);
    }

    public void topoSort() {

        int[] indegree = new int[vertices];

        // Calculate indegree
        for (int i = 0; i < vertices; i++) {
            for (int node : graph.get(i)) {
                indegree[node]++;
            }
        }

        Queue<Integer> q = new LinkedList<>();

        // Add nodes with indegree 0
        for (int i = 0; i < vertices; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }

        System.out.print("Topological Order: ");

        while (!q.isEmpty()) {
            int node = q.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                indegree[neighbor]--;

                if (indegree[neighbor] == 0) {
                    q.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {

        TopologicalSort g = new TopologicalSort(6);

        g.addEdge(5, 0);
        g.addEdge(5, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 1);
        g.addEdge(0, 4);

        g.topoSort();
    }
}

Applications of Topological Sort

• Course scheduling
• Task management systems
• Build systems (compilers)
• Job scheduling
• Dependency resolution

DFS vs Kahn’s Algorithm

FAQ – Questions & Answers

What is Topological Sort?

Topological Sort is a way to order nodes in a directed graph based on dependencies.

Where is Topological Sort used?

It is used in scheduling, course planning, and dependency resolution.

Can Topological Sort work on a cyclic graph?

No, it only works on a DAG (Directed Acyclic Graph).

What is time complexity?

O(V + E)