Skip to main content

Topological Sort – Short Notes

  • use when: DAG (Directed Acyclic Graph) and you want a valid order of nodes
  • example: course schedule, task ordering with dependencies

approaches:​

1. DFS​

  • do a normal DFS
  • after visiting all descendants of a node, add to output
  • finally reverse the output
  • cycle detection: track recursion stack (using visiting set or color array)
  • if we revisit a node already in visiting → cycle
def dfs(u):
    if u in visiting:
        cycle = True
        return
    if u in visited:
        return
    visiting.add(u)
    for v in graph[u]:
        dfs(v)
    visiting.remove(u)
    visited.add(u)
    op.append(u)

2. Kahn’s Algorithm (BFS)​

  • maintain in-degree of each node
  • push nodes with 0 in-degree to a queue
  • pop from queue, reduce in-degree of neighbors
  • if neighbor's in-degree becomes 0 → push to queue
  • if final output has less than n nodes → cycle exists
q = deque(nodes with in-degree 0)
while q:
    u = q.popleft()
    op.append(u)
    for v in graph[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            q.append(v)

time and space​

  • both approaches: O(n + e)
  • n = number of nodes
  • e = number of edges

notes:​