Ricardo Borges

Personal blog

Topological sort

Topological sort is an ordering of the vertices of a directed acyclic graph, in a way that if there is an edge from a vertex A to B, then A comes before B. For example, let's say there is a set of projects and some of them depend on other projects:

graph

In this example project B and C depends on project A, and project D depends on projects B and C. Therefore, project A must be executed first, then projects B and C, and finally project D. Resulting in this order: A, B, C, D or A, C, B, D.

Note that we start from node A because it doesn't have dependencies and repeat it, that is after A is done, B and C haven't dependencies anymore, so we can choose either one to be the next. That's why this algorithm works only on acyclic graphs.

We can use a modified depth-first search for this algorithm, here I talk more about DPS. The steps are the following:

1 - For every unvisited node visit it and its adjacent nodes (DPS) 2 - After visiting a node and its adjacent add it at the beginning of a list (you can use a stack instead), this list will be in the topological order.

Here's an implementation in TypeScript, I'm using this implementation of a graph:

1function topSort(
2  node: Node<number>,
3  visited: Map<number, boolean>,
4  order: number[]
5) {
6  if (!node) return;
7
8  // set node as visited
9  visited.set(node.data, true);
10
11  // for each of node's unvisited adjacent call topSort
12  node.adjacent.forEach((item) => {
13    if (!visited.has(item.data)) {
14      topSort(item, visited, order);
15    }
16  });
17
18  // add node at the beginning of the order list
19  order.unshift(node.data);
20}
21
22// topological order list
23const order = [];
24// map to keep track of visited nodes
25const visited = new Map();
26
27// For every unvisited node visit it and its adjacent nodes
28for (const entry of graph.nodes.entries()) {
29  const node = entry[1];
30  if (!visited.has(node.data)) {
31    topSort(node, visited, order);
32  }
33}

There are other problems that topological sorting can resolve, like the order that courses have to be selected during college, since they may have other courses as a prerequisite. Or even the order of steps of a recipe, in which some must be taken before others.

There are a lot of explanations for this algorithm on the internet, here I tried to explain it in a little different way, I hope this helped you to make sense of it or if you haven't heard about topological sorting before, at least this may be an introduction of it.