There are two ways to do topological sorts:

DFS

To perform a topological sort via DFS, you will need the following:

• Adjacency Lists
• A "visited" set
• Recursion

Recall that DFS itself will not give you nodes in topological ordering. You have to modify DFS so that you push nodes into an array when they have no neighbors left (leaf nodes). This ensures that the children gets added before the parent, which if done recursively, will present you with a list of nodes in topological order.

BFS

To do topological sort via BFS, you will need two things:

• Adjacency Lists
• In-degree array (or map)

The N-degree (or in-degree) array is a mapping of indices (the vertex ID) to the count of incoming graph edges.

This N-degree array is used to maintain the number of edges that are still attached to a given vertex.

1. To make the N-degree array, allocate an array of 0s. Add 1 to the count for a given vertex when you create the adjacency list.
2. Start filling the queue with vertices that have N-degree = 0
3. Loop through the queue. Dequeue from the queue to get the current vertex. Look up the neighbors of the current vertex and decrement their N-degree counts by 1. Add them to the queue (BFS) only if their N-degree is now 0. After evaluating the neighbors, the processing for the current vertex is complete, and we add 1 to the total count.
4. Repeat #3 until all nodes are explored. If a cycle is present, then some node N-degree counts will never reach all the way down to 0, resulting in total being less than the number of vertices in the entire graph.

Example:

        adj_map = defaultdict(list)
        n_degrees = [0 for i in range(0, numCourses)] 

        for edges in prerequisites:
            adj_map[edges[1]].append(edges[0])
            n_degrees[edges[0]] += 1

        total = 0

        if not prerequisites:
            return True

        q = deque([])

        for i in range(0, numCourses):
            if n_degrees[i] == 0:
                q.append(i)

        while q:
            curr = q.popleft()

            for neighbor in adj_map[curr]:
                n_degrees[neighbor] -= 1
                if n_degrees[neighbor] == 0:
                    q.append(neighbor)

            total += 1

        return total == numCourses