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:
function topSort(
node: Node<number>,
visited: Map<number, boolean>,
order: number[]
) {
if (!node) return;
// set node as visited
visited.set(node.data, true);
// for each of node's unvisited adjacent call topSort
node.adjacent.forEach((item) => {
if (!visited.has(item.data)) {
topSort(item, visited, order);
}
});
// add node at the beginning of the order list
order.unshift(node.data);
}
// topological order list
const order = [];
// map to keep track of visited nodes
const visited = new Map();
// For every unvisited node visit it and its adjacent nodes
for (const entry of graph.nodes.entries()) {
const node = entry[1];
if (!visited.has(node.data)) {
topSort(node, visited, order);
}
}
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.
Top comments (0)