Topological Sort: Definition, Example, and Use Cases

A topological sort is an ordering of the nodes in a directed graph where each node appears before all nodes it points to. It is used only on graphs without cycles, called Directed Acyclic Graphs (DAGs). This ordering helps to represent dependencies clearly, like task scheduling or build systems.

How It Works

Imagine you have a list of tasks where some tasks must be done before others. Topological sort arranges these tasks in a sequence so that every task comes before the tasks that depend on it. It works only if there are no circular dependencies, meaning you can't have a task that depends on itself indirectly.

The process involves looking for tasks with no prerequisites, placing them first, and then removing them from the list. Then, it repeats this for the remaining tasks until all are ordered. This is like organizing steps in a recipe where you must prepare ingredients before cooking.

Example

This example shows a simple topological sort on a graph representing tasks with dependencies.

python

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([node for node in indegree if indegree[node] == 0])
    order = []

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

    if len(order) == len(graph):
        return order
    else:
        return "Graph has a cycle, no topological order exists"

# Example graph: keys are tasks, values are tasks that depend on the key
example_graph = {
    'cook': ['eat'],
    'shop': ['cook'],
    'eat': [],
    'clean': ['shop']
}

result = topological_sort(example_graph)
print(result)

Output

['clean', 'shop', 'cook', 'eat']

When to Use

Topological sort is useful when you need to order tasks that depend on each other. For example, it helps in:

• Scheduling jobs where some must finish before others start.
• Resolving dependencies in software package installation.
• Planning course prerequisites in education.
• Building systems where some files must compile before others.

It only works if there are no circular dependencies, so it also helps detect cycles in dependency graphs.

Key Points

• Topological sort orders nodes so all dependencies come first.
• It applies only to Directed Acyclic Graphs (DAGs).
• Commonly used in task scheduling and dependency resolution.
• Detects cycles by failing to produce a full ordering.

Key Takeaways

Topological sort arranges tasks so each comes before tasks depending on it.

It works only on graphs without cycles, called DAGs.

Useful for scheduling, dependency resolution, and detecting cycles.

The algorithm repeatedly removes nodes with no incoming edges.

If a cycle exists, no valid topological order can be found.