Topo Sort

WHAT IS TOPO SORT?

Topological Sort (Topo Sort) ek tarike ka sequence banane jaisa hai jaha kuch tasks ko dusre tasks se pehle complete karna zaroori hota hai. Directed Acyclic Graph (DAG) me, ye ensure karta hai ki agar ek edge u se v tak hai, to u sequence me v ke pehle aayega. Ye task scheduling, compilers me dependencies resolve karne, aur workflows ke steps ka order decide karne jaise kaamon me kaafi useful hai.

Preconditions:

• Graph must be Directed and Acyclic (DAG).
• Applicable only on DAGs; cycles will invalidate the topological order.

DFS approach =>

1. Create a visited array of size V.
2. Run DFS for all unvisited nodes.
3. In DFS:

• Mark node visited.
• Recursively visit all its unvisited adjacent nodes.
• After visiting all neighbours, push current node into a stack.

1. At the end, pop from stack to get topological order.

BFS approach or Kahn's Algorithm =>

🔹 Core Idea:

1. Count the in-degree (number of incoming edges) for each vertex.
2. Insert all vertices with in-degree = 0 into a queue (they have no dependencies).
3. Process the queue:

• Pop a node from the queue and add it to the topological ordering.
• For each neighbor, decrease its in-degree by 1.
• If any neighbor’s in-degree becomes 0, push it into the queue.

1. Repeat until the queue is empty.

Steps:

• Create an array inDegree[] of size V initialized to 0.
• Traverse adjacency list to fill in-degrees.
• Use a queue to store nodes with in-degree = 0.
• While the queue is not empty:
• Pop a node, add to answer list.
• Decrease in-degree of all adjacent nodes.
• If any adjacent node’s in-degree becomes 0, push it into the queue.

When to Use Topological Sort:

🔹 Use Cases:

• Task Scheduling (tasks with dependencies)
• Course Prerequisites
• Build Systems (build A before B)
• Compilation Order
• Dependency Resolution
• Package Managers
• Job Scheduling