Topological Sort orders nodes so that for every directed edge A → B, node A comes before B. It only works on DAGs (Directed Acyclic Graphs). 📋
💡 Think of it like this: You're planning your college courses. Some courses have prerequisites (you must take Math before Physics). Topological sort gives you a valid order to take ALL courses!
# Course example:
# Math → Physics → Quantum Physics
# Math → CompSci → AI
# Valid order: Math, Physics, CompSci, Quantum Physics, AI
# Another valid: Math, CompSci, Physics, AI, Quantum Physics
Kahn's Algorithm (BFS-based):
from collections import deque, defaultdict
def topological_sort(num_nodes, edges):
graph = defaultdict(list)
in_degree = [0] * num_nodes
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nei in graph[node]:
in_degree[nei] -= 1
if in_degree[nei] == 0:
queue.append(nei)
return order if len(order) == num_nodes else [] # Empty = cycle!
Complexity: Time O(V + E), Space O(V + E). Used in: course scheduling, build systems, package managers, task dependency resolution.
📋 Instructions
Perform topological sort using Kahn's algorithm.
Graph: 6 nodes, edges: [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]]
Print one valid topological ordering.
Build adjacency list and in-degree map. Start with nodes having in-degree 0. Process queue, decrementing neighbors' in-degree.