Kahn's Algorithm

Created on 2020-12-27T20:40:45-06:00

Return to the Index

This card pertains to a resource available on the internet.

This card can also be read via Gemini.

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)