---
title: Topological Sort
description: 'Topological sort or topological ordering of a directed graph is an ordering of nodes such that every node appears in the ordering before all the nodes it points to. '
hidden: true
---

## Directed Graph

Before we get started on topological order, let's talk about directed graphs first. A graph is directed when its edges have directions (these edges are also called arcs). Suppose that v, w are vertices in a directed graph. Let's get familiar with a few concepts.

- **in-edge** - an edge pointing to or coming into the node
- **out-edge** - an edge pointing away or going out from the node (we will refer those nodes on the other end of the out-edges of v to v's neighbors)
- **in-degree** - the number of in-edges coming into the node
- **out-degree** - the number of out-edges going out from the node
- **dependency** - "v depends on w" / "v is dependent on w" means that there is a directed path from w to v where v, w are vertices in a directed graph. With these new terms under our belt, it will make more sense when we talk about directed graphs.

## What is a topological order?

Topological sort is not unique. For example, for a graph like this:

![Topological sort example](/blume-assets/content/public/topo_intro_1.png)

Both `[4, 5, 2]` and `[5, 4, 2]` are valid topological orders. 

![Topological sort example](/blume-assets/content/public/topo_intro_2.png)

Task 3 is completely independent of task 2 and 4, and it can be anywhere in the order as long as it is before task 1 which depends on it. All of the following ordering are valid topological orderings.

`[4, 2, 3, 1], [4, 3, 2, 1], [3, 4, 2, 1]`


:::warning[Graphs with Cycles Do Not Have Topological Ordering]
It should be obvious that if a graph with a cycle does not have a topological ordering. In the above example, 2 has to come before 5 which has come before 4 which has to come before 2 which has to come before 5... which is impossible.
:::

## Kahn's Algorithm

To obtain a topological order, we can use Kahn's algorithm which is very similar to Breadth First Search.

In order to understand why we must use this algorithm we first look at the problem it is trying to solve.

Given a directed graph does there exist a way to remove the nodes such that each time we remove a node we guarantee that no other nodes point to that particular node?

For this algorithm, we systematically remove one node at a time, each time removing a node such that no other nodes point to that node (in-degree is 0). If no such node exists, then there must be a cycle, and there is no way to order the nodes such that "every node appears in the ordering before all the nodes it points to" (no solution). After removing the current node, for each neighboring node the current node points to, we check whether any nodes point to this node. If there isn't any, we push this node into the queue. Notice it is important to keep track of the number of nodes pointing to a node (in-degree) in the question as we only push the node into the queue once all nodes the current node depended on have been removed. 

Here is a graphic to demonstrate the idea.

<Carousel>
<CarouselImage src='../../../public/topo_kahn.001.png' />
<CarouselImage src='../../../public/topo_kahn.002.png' />
<CarouselImage src='../../../public/topo_kahn.003.png' />
<CarouselImage src='../../../public/topo_kahn.004.png' />
<CarouselImage src='../../../public/topo_kahn.005.png' />
<CarouselImage src='../../../public/topo_kahn.006.png' />
<CarouselImage src='../../../public/topo_kahn.007.png' />
<CarouselImage src='../../../public/topo_kahn.009.png' />
<CarouselImage src='../../../public/topo_kahn.010.png' />
</Carousel>

##  Example Code

:::tip
Notice the topological sort algorithm is very similar to BFS. The main difference is that we only push nodes with 0 in-degree into the queue in topological sort whereas in BFS we push all the neighboring nodes into the queue.
:::

```py
from collections import deque

def find_indegree(graph):
    indegree = { node: 0 for node in graph }  # dict
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1
    return indegree


def topo_sort(graph):
    res = []
    q = deque()
    indegree = find_indegree(graph)
    for node in indegree:
        if indegree[node] == 0:
            q.append(node)
    while len(q) > 0:
        node = q.popleft()
        res.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    return res if len(graph) == len(res) else None
```