# Topological Sort — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/g-topo

> Order with dependencies.

## Kahn's algorithm

A **topological order** lists nodes of a directed acyclic graph so every edge points forward: courses after their prerequisites, build steps after dependencies. Kahn's algorithm repeatedly takes nodes with **in-degree zero**, removing their outgoing edges. If some nodes are never processed, the graph has a **cycle** and no valid order exists. DFS with post-order is the alternative.

## Ordering courses and detecting a cycle, run

I ran this with Python 3.12.3 (standard library only). Four courses get a valid order; two courses that require each other return an empty list.

```python
# Topological sort (Kahn's algorithm): course prerequisites
from collections import deque

def course_order(n, prereqs):
    graph, indeg = [[] for _ in range(n)], [0] * n
    for course, pre in prereqs:
        graph[pre].append(course)
        indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == n else []   # empty: a cycle exists

print(course_order(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))
print(course_order(2, [(1, 0), (0, 1)]))
```

Output:

```
[0, 1, 2, 3]
[]
```

## Get the edge direction right

Decide clearly whether an edge means "prerequisite to course" or the reverse; mixing them is the common bug.

**Quiz:** How does Kahn's algorithm detect a cycle?

- [x] Not all nodes get processed because some never reach in-degree zero
- [ ] The queue overflows
- [ ] A node is visited twice
- [ ] The graph has more edges than nodes

*Answer:* Not all nodes get processed because some never reach in-degree zero. Cycles keep in-degrees positive.