##### Updated on March 6, 2021

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.

- 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.
- Start filling the queue with vertices that have N-degree = 0
- 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. - 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
```