This content originally appeared on DEV Community and was authored by Ricardo Borges
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.
This content originally appeared on DEV Community and was authored by Ricardo Borges
Ricardo Borges | Sciencx (2021-07-08T18:52:01+00:00) Topological sort. Retrieved from https://www.scien.cx/2021/07/08/topological-sort/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.