DSA Topological Sort

Topological sort arranges the nodes of a directed graph in a line so that every arrow points forward. Each task appears after all the tasks it depends on. The method answers the question: "In what order should I do these things?"

Consider getting dressed in the morning. Socks must go on before shoes. A shirt must go on before a jacket. Many valid orders exist, yet some orders break the rules. Topological sort finds an order that respects every rule.

Directed Acyclic Graphs

The method needs a directed acyclic graph, shortened to DAG. Directed means every edge has a direction. Acyclic means no loops exist. A loop such as A needs B, B needs C, and C needs A makes a valid order impossible.

Course prerequisites

Maths -> Algebra -> Calculus
Programming -> DSA

One valid order:
Maths, Programming, Algebra, DSA, Calculus

Kahn's Algorithm

Kahn's algorithm builds the order by repeatedly removing tasks with no waiting prerequisites. The in-degree of a node counts the arrows pointing into it. A node with in-degree 0 has nothing blocking it.

• Count the in-degree of every node.
• Place all nodes with in-degree 0 into a queue.
• Remove one node from the queue and add it to the result.
• Lower the in-degree of each neighbor by one. A neighbor that reaches 0 joins the queue.
• Repeat until the queue empties.

The Code

from collections import deque

def topological_sort(graph):
    indegree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1

    queue = deque([n for n in indegree if indegree[n] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) == len(graph):
        return order
    return []

courses = {
    "Maths": ["Algebra"],
    "Algebra": ["Calculus"],
    "Programming": ["DSA"],
    "Calculus": [],
    "DSA": []
}
print(topological_sort(courses))
# ['Maths', 'Programming', 'Algebra', 'DSA', 'Calculus']

Step-by-Step Trace

In-degrees: Maths 0, Algebra 1, Programming 0, Calculus 1, DSA 1

Queue: [Maths, Programming]
Take Maths        -> Algebra becomes 0     Queue: [Programming, Algebra]
Take Programming  -> DSA becomes 0         Queue: [Algebra, DSA]
Take Algebra      -> Calculus becomes 0    Queue: [DSA, Calculus]
Take DSA          -> nothing changes       Queue: [Calculus]
Take Calculus     -> nothing changes       Queue: []

Order: Maths, Programming, Algebra, DSA, Calculus

Detecting a Cycle

A cycle keeps some nodes from ever reaching in-degree 0. The result list comes out shorter than the node count. The code above returns an empty list in that case, which signals that no valid order exists.

loop = {"A": ["B"], "B": ["C"], "C": ["A"]}
print(topological_sort(loop))   # []

Real-Life Uses

Build tools compile code files in dependency order. Package managers install libraries before the programs that need them. Universities check that course plans respect prerequisites. Project planners schedule tasks so every task starts after its requirements finish. Spreadsheet programs recalculate cells in an order that respects formula links.

More Than One Valid Order

Many graphs allow several correct orders. In the course example, Programming could come before Maths and the order would stay valid. The algorithm returns one of them, based on the queue order. A problem that demands a specific order, such as the alphabetically smallest, needs a priority queue in place of the plain queue.

Depth-First Alternative

A second method runs depth-first search and adds each node to a list after all its neighbors finish. Reversing that list produces a valid order. Kahn's approach feels easier to follow for beginners, and it detects cycles without extra code.

Common Mistakes

Running the method on an undirected graph makes no sense, because edges need direction. Forgetting nodes that appear only as destinations leaves them out of the in-degree table. Add every node to the dictionary, even with an empty neighbor list. Always check the result length to catch cycles.

Complexity Summary

• Time: O(V + E), where V counts nodes and E counts edges.
• Space: O(V) for the in-degree table and the queue.

Key Points

• Topological sort orders tasks so dependencies come first.
• The graph must be directed and free of cycles.
• In-degree counts the arrows pointing into a node.
• Kahn's algorithm removes nodes with in-degree 0 one at a time.
• A short result list reveals a cycle.
• Several valid orders may exist.