@rkenmi - Topological Sorting

Topological Sorting

Topological Sorting

Back to Top

Updated on March 6, 2021

There are two ways to do topological sorts:


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.


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.


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

        for edges in prerequisites:
            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:

        while q:
            curr = q.popleft()

            for neighbor in adj_map[curr]:
                n_degrees[neighbor] -= 1
                if n_degrees[neighbor] == 0:

            total += 1

        return total == numCourses

Article Tags:
unlisteddfsbfsgraph traversalgraphtopological sortdag