Editing Topological sorting (section)

===Kahn's algorithm===
{{Distinguish|Kuhn's algorithm}}
One of these algorithms, first described by {{harvp|Kahn|1962}}, works by choosing vertices in the same order as the eventual topological sort.{{r|Kahn}} First, find a list of "start nodes" that have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty (finite) acyclic graph. Then:

 ''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)''

If the graph is a [[Directed acyclic graph|DAG]], a solution will be contained in the list L (although the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sort is impossible.

Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created. A variation of Kahn's algorithm that breaks ties [[lexicographic order|lexicographically]] forms a key component of the [[Coffman–Graham algorithm]] for parallel scheduling and [[layered graph drawing]].