RavnaryA Knowledge Platform
Colour theme

Card 02/ 08

Take the quiz

WalkthroughDifficulty: Intermediate3 min

Trace Kahn's Algorithm With In-Degrees and a Queue of Ready Tasks

Output a task with no unmet dependencies, lower the count of everything that waited on it, and repeat.

Kahn's algorithm builds a topological order by repeatedly outputting a vertex with no unmet dependencies. It keeps each vertex's in-degree, the number of edges into it from vertices not yet output, and a queue of ready vertices, those whose count is 0. This walkthrough runs it on the topic's graph, edges D->A, D->B, C->B, A->F, B->F and B->E, with ready vertices joining the queue in alphabetical order.

The steps are: count every vertex's in-degree; put each vertex with a count of 0 in the queue; then, until the queue is empty, take the front vertex, output it, and lower by one the count of every vertex it has an edge to, adding any that reach 0 to the queue.

The in-degrees start at A 1, B 2, C 0, D 0, E 1 and F 2. Predict the output order before reading the trace.

C D A B E F. C and D are ready from the start. B becomes ready only after both C and D are out, and F only after both A and B.

In the trace below each cell shows a vertex and its count, or out once it has been output, and the marker is on the vertex just output. The trace is from a run.

In-degrees as Kahn's algorithm outputs each vertex of the topic's graph

InputEdges D->A, D->B, C->B, A->F, B->F and B->E; ready vertices taken in alphabetical order

  1. Start

    1. A:1
    2. B:2
    3. C:0
    4. D:0
    5. E:1
    6. F:2

    Each cell is a vertex and its in-degree, the number of its dependencies not yet output. C and D have none, so both start in the queue, in alphabetical order.

  2. Output C

    1. A:1
    2. B:1
    3. C:outnext
    4. D:0
    5. E:1
    6. F:2

    C leaves the queue and is output. Its one edge goes to B, whose count drops from 2 to 1, so B still waits on D.

  3. Output D

    1. A:0
    2. B:0
    3. C:out
    4. D:outnext
    5. E:1
    6. F:2

    D is output. A drops to 0 and B to 0, so both join the queue, A first because D's neighbours are taken in alphabetical order.

  4. Output A

    1. A:outnext
    2. B:0
    3. C:out
    4. D:out
    5. E:1
    6. F:1

    A is output, and F drops to 1: it still waits on B.

  5. Output B

    1. A:out
    2. B:outnext
    3. C:out
    4. D:out
    5. E:0
    6. F:0

    B is output. E and F both reach 0 and join the queue.

  6. Output E

    1. A:out
    2. B:out
    3. C:out
    4. D:out
    5. E:outnext
    6. F:0

    E is output. It has no outgoing edges, so nothing changes but the output.

  7. Output F

    1. A:out
    2. B:out
    3. C:out
    4. D:out
    5. E:out
    6. F:outnext

    F is output, the queue is empty, and all six vertices are out: the order is C D A B E F.

ResultOutput C D A B E F, all six vertices

The order is C D A B E F, and every edge points forwards in it. The rule that makes this work is that a vertex joins the queue only when its count reaches 0, which is the moment its last dependency is output. B's count fell to 1 when C went out, but B did not join then, because D still had to go first. So no vertex is ever output before something it depends on.

Each vertex joins the queue once and each edge lowers one count once, so the algorithm runs in O(V + E). Counting the in-degrees at the start is one more pass over the edges, which does not change that.

← → move through sections and cards