Topological sorting Algorithm

To sort a graph in topologic order. Graph must be acyclic(without cycle)

• Complexity => O(n+m)

// Table with the indegree of each node
INDEGREE_LIST

// Queue list of nodes initially empty
NODES_QUEUE = {} 

// Put each node that has indegree of 0 in queue of nodes
for node in GRAPH.nodes

    if  INDEGREE_LIST[node] == 0
        NODES_QUEUE.push(node)

// If queue of nodes is still empty, we have a cycle. Return indegree list and False
if NODES_QUEUE.isEmpty()
    
    return (FALSE, INDEGREE_LIST)

// Counter for number of sorted nodes in topological order
topo_node_counter = 0

// Principal part of the algorithm
while NODES_QUEUE.isNotEmpty()

    // Get the first node with 0 indegree
    zero_indegree_node = NODES_QUEUE.pop()

    // Put the node in the new sorted indegree table
    INDEGREE_SORTED_LIST[++topo_node_counter] = zero_indegree_node

    for adjacent to zero_indegree_node

        // Remove arc from indegree table
        INDEGREE_LIST[adjacent]--

        // If indegree of adjacent becomes 0, insert in the queue
        if INDEGREE_LIST[adjacent] == 0

            NODES_QUEUE.push(adjacent)

// Checking if there is a cycle or not
if topo_node_counter != GRAPH.nodes
    
    return (FALSE, INDEGREE_SORTED_LIST)

return (TRUE, INDEGREE_SORTED_LIST)