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:
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.
