algorithms.live
    DSA
    intermediate

    Topological Sort

    Software Engineer path · lesson 27 of 99
    time O(V+E)
    space O(V+E)

    Directed, like A>B meaning A must come before B. Badges show remaining in-degree.

    Try:
    Ain 0Bin 1Cin 1Din 2Ein 1Fin 1
    queue
    order
    CurrentReady / waitingJust became readyFinalStuck in a cycle

    Count each node’s incoming edges.

    Code (running line highlighted)
    1. 1indeg[v] = number of edges into v
    2. 2queue = every v with indeg[v] == 0
    3. 3while queue:
    4. 4 u = queue.popleft(); order.append(u)
    5. 5 for v in out(u): indeg[v] -= 1; if indeg[v] == 0: queue.append(v)
    6. 6if len(order) < n: the graph has a cycle
    Nodes output
    0 / 6
    Edges removed
    0 / 6

    Tap any element in the diagram to inspect its state at this step.

    1 / 15

    Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.

    Kahn’s algorithm

    Sequence

    Order the steps of a topological sort by in-degree.

    Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.

    1. 1Drop a step here
    2. 2Drop a step here
    3. 3Drop a step here
    4. 4Drop a step here
    5. 5Drop a step here
    5 pieces left to place

    Test your knowledge

    20 questions
    Question 1 of 20
    Score: 0

    Topological Sort is only possible for which type of graph?

    Write the code

    Runs your solution

    Course Schedule II

    Return the ordering of courses you should take to finish all courses given the prerequisites. Return an empty array if impossible.

    Example Cases

    Input:[2, [[1,0]]]
    Output:[0,1]
    Input:[4, [[1,0],[2,0],[3,1],[3,2]]]
    Output:[0,1,2,3]
    javascript
    function findOrder(numCourses, prerequisites) {
  // Your code here
}

    The short version

    Think of getting dressed. You must put on socks before shoes, and underwear before pants. You can't just put things on in random order; dependencies must be respected.

    In more depth

    Order of Operations

    Topological Sorting is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering.

    Prerequisite: The graph must be a Directed Acyclic Graph (DAG). If there is a cycle (A -> B -> A), no linear ordering is possible.

    Kahn's Algorithm (BFS):

    1.Calculate In-Degree of all nodes.
    2.Add nodes with In-Degree 0 to a queue.
    3.Process queue: remove node, decrement neighbor In-Degrees. If neighbor becomes 0, add to queue.

    When to reach for this

    • Scheduling tasks with dependencies
    • Build systems (compiling dependencies first)
    • Detecting cycles in a directed graph

    Interview Questions

    Amazon
    Microsoft
    LinkedIn
    Meta
    Google
    Microsoft
    Amazon
    Palantir
    LinkedIn
    Netflix
    Bloomberg
    Uber

    References & Further Reading

    Topological Sort Algorithm | DFSYouTube · takeUforward
    video
    Topological sortingWikipedia
    article
    Directed acyclic graphWikipedia
    article
    All Data Structures & Algorithms topics

    Love this visualization?

    Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.

    100% free • No credit card required