This guide explains Topological Sorting from first principles. The goal is to understand the problem it solves, why the algorithm works, how to implement it, and where it appears in real software systems.
What problem does it solve?
Topological Sorting belongs to the graph-algorithm toolbox. Before coding, define what the vertices represent, what an edge means, and what result the system actually needs.
The core idea in simple terms
اگر B به A وابسته باشد، A باید قبل از B قرار گیرد. Kahn این کار را با indegree انجام میدهد.
Step-by-step process
- indegree همه رأسها را حساب میکنیم.
- رأسهای indegree صفر را وارد Queue میکنیم.
- هر رأس را برداشته و indegree همسایهها را کم میکنیم.
- اگر همه پردازش نشوند، cycle وجود دارد.
JavaScript example
function topoSort(graph) {
const indegree = {};
for (const u of Object.keys(graph)) indegree[u] ??= 0;
for (const u of Object.keys(graph))
for (const v of graph[u]) indegree[v] = (indegree[v] ?? 0) + 1;
const q = Object.keys(indegree).filter(x => indegree[x] === 0), out = [];
while (q.length) {
const u = q.shift(); out.push(u);
for (const v of graph[u] ?? []) if (--indegree[v] === 0) q.push(v);
}
return out.length === Object.keys(indegree).length ? out : null;
}Real-world and workplace examples
- ترتیب Build Packageها
- Prerequisite درسها
- CI/CD Jobs
- Workflow و ETL
Time and space complexity
O(V + E) time و O(V) space
When should you use it?
Use it when the problem matches this condition: Dependencyهای جهتدار بدون چرخه.
When is it not a good fit?
It is usually not the best choice when: در گراف دارای cycle ترتیب توپولوژیک کامل نداریم..
Summary
Do not choose an algorithm by name alone. First identify whether the graph is directed or undirected, weighted or unweighted, and whether the goal is traversal, reachability, shortest path, connectivity, spanning structure, or combinatorial optimization.