Topological Sort

Analogy categoryAnalogies

Introduction

Topological sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u appears before vertex v in the ordering. It only makes sense for DAGs — a graph with a cycle has no valid topological order, since a cycle would require a vertex to come both before and after itself. Common applications include task scheduling with dependencies, build systems, and course prerequisite ordering.

🏏

Cricket analogy: A net-practice schedule where a bowler must finish fitness testing before batting drills, and batting drills before a simulation match, is a DAG; but if fitness testing requires the simulation match first, you get an impossible cycle with no valid order.

Representation/Syntax

python

from collections import deque, defaultdict

def topological_sort_kahn(vertices, edges):
    graph = defaultdict(list)
    in_degree = {v: 0 for v in vertices}

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([v for v in vertices if in_degree[v] == 0])
    order = []

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

    if len(order) != len(vertices):
        raise ValueError('Graph has a cycle; topological sort not possible')
    return order

Explanation

Kahn's algorithm is a BFS-based approach: it first computes the in-degree (number of incoming edges) of every vertex, then repeatedly removes vertices with in-degree zero (meaning all their prerequisites are satisfied), appending them to the result and decrementing the in-degree of their neighbors. If the resulting order contains fewer vertices than the graph has, a cycle exists and no valid ordering is possible. An alternative DFS-based approach performs a standard DFS and prepends each vertex to the result only after all of its descendants have been fully explored (i.e., on 'finish' time), which naturally produces edges pointing forward.

🏏

Cricket analogy: Kahn's approach is like clearing net-practice slots: count how many prerequisite drills each player still owes, release players with zero pending drills first, then decrement counts for whoever depended on them; the DFS approach instead fully finishes one player's entire drill chain before recording them, working backward from 'done'.

Example

python

def topological_sort_dfs(vertices, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = set()
    temp_mark = set()  # nodes on the current DFS path, for cycle detection
    order = []

    def visit(node):
        if node in temp_mark:
            raise ValueError('Graph has a cycle; topological sort not possible')
        if node not in visited:
            temp_mark.add(node)
            for neighbor in graph[node]:
                visit(neighbor)
            temp_mark.remove(node)
            visited.add(node)
            order.append(node)  # append on finish

    for v in vertices:
        if v not in visited:
            visit(v)

    return order[::-1]  # reverse finish order

vertices = ['shirt', 'jacket', 'pants', 'belt', 'shoes', 'socks']
edges = [('shirt', 'jacket'), ('pants', 'jacket'), ('pants', 'belt'), ('belt', 'shoes'), ('socks', 'shoes')]

print('Kahn:', topological_sort_kahn(vertices, edges))
print('DFS:', topological_sort_dfs(vertices, edges))

Complexity

Both Kahn's algorithm and the DFS-based approach run in O(V + E) time: Kahn's processes each vertex once via the queue and each edge once when decrementing in-degrees; the DFS approach visits each vertex and edge exactly once. Space complexity is O(V + E) for the graph plus O(V) for the in-degree map, visited set, and result order. Topological order is generally not unique — multiple valid orderings can exist when several vertices simultaneously have zero remaining dependencies.

🏏

Cricket analogy: Both scheduling methods for net sessions take time proportional to the number of players plus dependency links, O(V + E), and need extra space for the same total plus a dependency counter, O(V + E); and since several players might simultaneously have zero pending drills, more than one valid practice order can exist.

Key Takeaways

Topological sort only applies to Directed Acyclic Graphs (DAGs); a cycle means no valid ordering exists.
Kahn's algorithm (BFS-based) repeatedly removes zero-in-degree vertices and tracks in-degree counts.
The DFS-based approach appends vertices to the result on 'finish' and reverses the final list.
Both approaches run in O(V + E) time and O(V) extra space.
If Kahn's algorithm processes fewer than V vertices, the graph contains a cycle.

Practice what you learned

1. What type of graph is required for topological sort to be valid?

2. In Kahn's algorithm, which vertices are initially added to the queue?

3. How can you detect a cycle using Kahn's algorithm?

4. In the DFS-based topological sort, when is a vertex added to the result list?

5. What is the time complexity of Kahn's algorithm for topological sort?

Was this page helpful?

Minimum Spanning Tree

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#TopologicalSort#Topological#Sort#Representation#Syntax#Algorithms#StudyNotes#SkillVeris