 Topological sorting is the <unk> problem of finding a topological ordering of a given DAG . It can be solved in linear time . Kahn 's algorithm for topological sorting builds the vertex ordering directly . It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering ; initially this list consists of the vertices with no incoming edges at all . Then , it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering , and checks whether its neighbors should be added to the list . The algorithm terminates when all vertices have been processed in this way . Alternatively , a topological ordering may be constructed by reversing a <unk> numbering of a depth @-@ first search graph <unk> . 
