Topological Sorting Visualization
Topological Sorting is an ordering of nodes in a directed acyclic graph (DAG) where each node appears before all the nodes it points to. It is like creating a list of tasks, ensuring that each task comes after any tasks it depends on. The sorting can be achieved using Kahn's algorithm or DFS with a stack. Kahn's algorithm works by repeatedly removing nodes with no incoming edges (zero in-degree) and adding them to the order.
Pseudocode
indeg = indegree()
stack = new Stack()
for each vertex v:
if indeg[v] == 0: stack.push(v)
while stack is not empty:
u = stack.pop()
add u to sorted list
for each neighbor v of u:
indeg[v] = indeg[v] - 1
if indeg[v] == 0: stack.push(v)
function indegree():
indeg = map vertex -> 0
for each vertex u:
for each neighbor v of u:
indeg[v] = indeg[v] + 1
return indeg
AI Summary
(5 credits)
Common Interview Questions
Why can Topological Sort only be performed on a Directed Acyclic Graph (DAG)?
If a graph contains a directed cycle (e.g. A → B → C → A), there is a circular dependency where no node can be placed first. Topological sorting orders vertices linearly such that for every directed edge u → v, u appears before v.
Explain Kahn's algorithm for Topological Sort using in-degree.
Kahn's algorithm computes the in-degree of all vertices. Vertices with in-degree 0 are pushed into a stack. As vertices are popped and added to the topological order, the in-degree of their neighbors is decremented. If a neighbor reaches 0 in-degree, it is added to the stack.
How do build automation tools (e.g. Webpack, Make, Bazel) utilize Topological Sort?
Build tools model package dependencies as a DAG. Topological sort determines the exact compilation order so that every module/library is compiled after all of its dependencies have been built.
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0