Topological Sorting

In the field of computer science directed graph, a topological sort or topological ordering of a linear ordering vertices is a directed cycles directed acyclic graph of its algorithms linear time such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no , that is, if it is a (DAG). Any DAG has at least one topological ordering, and are known for constructing a topological ordering of any DAG in .
The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, O(E+V)

There are two ways to implement topological sort, one is BFS and the other is DFS.

Template to implement topological sort by BFS

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge(in degree is 0)
while S is non-empty do
    remove a node n from S
    add n to tail of 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)

Template to implement topological sort by DFS

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes 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 (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L