Topological Sort Algorithm
In the realm of graph theory and algorithms, the Topological Sort Algorithm stands as a
fundamental method with versatile applications. It provides a systematic way to arrange the
nodes of a directed acyclic graph (DAG) such that for every directed edge (u, v), node u appears
before node v in the ordering. This ordering holds significance in tasks like project scheduling,
dependency resolution, and compiling. In this article, we delve into the intricacies of the
Topological Sort Algorithm, exploring its mechanics, use cases, and impact on various fields. We
will also see the topological sorting example that will help in better understanding.
What is Topological Sort
Topological sort is a technique used in graph theory to order the vertices of a directed acyclic
graph (DAG). It ensures that for every directed edge from vertex A to vertex B, vertex A comes
before vertex B in the ordering. This is useful in scheduling problems, where tasks depend on
the completion of other tasks. The algorithm begins by selecting a vertex with no incoming
edges, adding it to the ordering, and removing all outgoing edges from the vertex. This process
is repeated until all vertices are visited, and the resulting ordering is a topological sort of the
DAG.
Algorithm of a Topological Sort
Here’s a step-by-step algorithm for topological sorting using Depth First Search (DFS):
• Create a graph with n vertices and m-directed edges.
• Initialize a stack and a visited array of size n.
• For each unvisited vertex in the graph, do the following:
• Call the DFS function with the vertex as the parameter.
• In the DFS function, mark the vertex as visited and recursively call the DFS function for all
unvisited neighbors of the vertex.
• Once all the neighbors have been visited, push the vertex onto the stack.
• After all, vertices have been visited, pop elements from the stack and append them to
the output list until the stack is empty.
• The resulting list is the topologically sorted order of the graph.
Example of a Topological Sort
Here's an example:
Since node 1 points to nodes 2 and 3, node 1 appears before them in the ordering. And, since
nodes 2 and 3 both point to node 4, they appear before it in the ordering.
So [1, 2, 3, 4, 5] would be a topological ordering of the graph.
Can a graph have more than one valid topological ordering? Yep! In the example above, [1, 3, 2,
4, 5] works too.
Cyclic Graphs
Look at this directed graph with a cycle:
The cycle creates an impossible set of constraints—B has to be before and after D in the
ordering.
As a rule, cyclic graphs don't have valid topological orderings.
The Algorithm
How can we produce a topological ordering for this directed graph?
Well, let's focus on the first node in the topological ordering. That node can't have any incoming
directed edges; it must have an indegree ↴ of zero.
Why?
Because if it had incoming directed edges, then the nodes pointing to it would have to come
first.
So, we'll find a node with an indegree of zero and add it to the topological ordering.
That covers the first node in our topological ordering. What about the next one?
Once a node is added to the topological ordering, we can take the node, and its outgoing edges,
out of the graph.
Then, we can repeat our earlier approach: look for any node with an indegree of zero and add it
to the ordering.
This is a common algorithm design pattern:
1. Figure out how to get the first thing.
2. Remove the first thing from the problem.
3. Repeat.
Here's what this looks like on our graph. We'll grab a node with an indegree of 0, add it to our
topological ordering and remove it from the graph:
and repeat
and repeat
until we're
out of nodes.