What is Topological Sort?

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge from vertex 'u' to vertex 'v', 'u' comes before 'v' in the ordering. It's commonly used for scheduling tasks with dependencies.

Can a graph with a cycle have a topological sort?

No, a topological sort is only possible for Directed Acyclic Graphs (DAGs). If a graph contains a cycle, it's impossible to create a linear ordering that satisfies the condition for all edges, as there would be a circular dependency.

Data Structures & Algorithms

Topological Sort

Ace your coding interviews by mastering Topological Sort. Our guide provides in-depth explanations, classic problems, and AI-driven feedback to help you solve any dependency-based problem.

Topological Sort (Kahn's Algorithm)

Here is a Python implementation of Topological Sort using Kahn's algorithm, which uses a queue-based approach.


from collections import deque

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque([u for u in in_degree if in_degree[u] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)

        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(topo_order) == len(graph):
        return topo_order
    else:
        return []  # Graph has a cycle

AI Coach Tip: Topological Sort is fundamental for problems involving task scheduling, course prerequisites, or any kind of dependency resolution. Remember that it only works on Directed Acyclic Graphs (DAGs). A common follow-up question is to detect a cycle if a valid topological sort cannot be found.