Topological sort

topological_sort.py

# graph is represented by adjacency list: List[List[int]]
# using DFS to find the topological sorting
def topological_sort(graph):
    # using a stack to keep topological sorting
    stack = []

    # set is used to mark visited vertices
    visited = set()

    def recur(current_vertex):
        # mark it visited
        visited.add(current_vertex)

        # Recur for all the vertices adjacent to current_vertex
        for v in graph[current_vertex]:
            if v not in visited:
                recur(v)

        # Push current vertex to stack after travelling to all neighbours
        stack.append(current_vertex)

    # call recur for all vertices
    for u in range(len(graph)):
        # Don't recur for u if it is already visited
        if u not in visited:
            recur(u)

    # print content of the stack
    print(stack[::-1])