The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, Kahn's algorithm One of these algorithms, first described by , works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty 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 DAG, a solution will be contained in the list L (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 lexicographically forms a key component of the Coffman–Graham algorithm for parallel scheduling and layered graph drawing. Depth-first search An alternative algorithm for topological sorting is based on depth-first search. The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node): L ← Empty list that will contain the sorted nodes while exists nodes without a permanent mark do select an unmarked node n visit(n) function visit(node n) if n has a permanent mark then return if n has a temporary mark then stop (graph has at least one cycle) mark n with a temporary mark for each node m with an edge from n to m do visit(m) remove temporary mark from n mark n with a permanent