Topological Sort Algorithm and Applications
Topological Sort
Welcome to Topological Sort, an algorithm for Directed Acyclic Graphs (DAGs). A topological sort is a linear ordering of a DAG's vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. This is incredibly useful for scheduling tasks with dependencies, such as a build process, course prerequisites, or project management.
1. The Core Idea: Ordering by Dependency
Imagine you have a list of tasks, where some tasks must be completed before others can begin. A topological sort gives you a valid sequence in which to perform these tasks.
It's important to note that a topological sort is only possible if the graph has no directed cycles. If a cycle exists (e.g., Task A depends on B, and B depends on A), then no valid ordering is possible.
There are two main algorithms for performing a topological sort: Kahn's Algorithm (which is BFS-based) and a DFS-based approach.
2. Kahn's Algorithm (BFS-based)
Kahn's algorithm works by identifying vertices that have no incoming edges (an in-degree of 0) and adding them to the sorted list. It then removes these vertices and their outgoing edges from the graph and repeats the process.
2.1. The Algorithm Step-by-Step
-
Compute In-degrees: Calculate the in-degree for every vertex in the graph.
-
Initialization:
- Create a queue and add all vertices with an in-degree of 0 to it.
- Create a list to store the sorted order.
-
Processing Loop:
- While the queue is not empty:
- Dequeue: Remove a vertex
ufrom the queue and add it to the sorted list. - Update Neighbors: For each neighbor
vofu:- Decrement the in-degree of
v. - If the in-degree of
vbecomes 0, addvto the queue.
- Decrement the in-degree of
- Dequeue: Remove a vertex
- While the queue is not empty:
-
Completion:
- If the sorted list contains
Nvertices, it is a valid topological sort. If it contains fewer thanNvertices, the graph has a cycle.
- If the sorted list contains
2.2. Implementation
function topologicalSortKahn(adj) {
const N = adj.length;
const inDegree = Array(N).fill(0);
for (let u = 0; u < N; u++) {
for (const v of adj[u]) {
inDegree[v]++;
}
}
const queue = [];
for (let i = 0; i < N; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
const sortedOrder = [];
while (queue.length > 0) {
const u = queue.shift();
sortedOrder.push(u);
for (const v of adj[u]) {
inDegree[v]--;
if (inDegree[v] === 0) {
queue.push(v);
}
}
}
if (sortedOrder.length !== N) {
throw new Error("Graph contains a cycle, topological sort not possible.");
}
return sortedOrder;
}
3. DFS-based Algorithm
This approach uses Depth-First Search. The key idea is that a vertex is added to the sorted list only after all its descendants have been visited.
3.1. The Algorithm Step-by-Step
-
Initialization:
- Create a
visitedset and a list to store the sorted order.
- Create a
-
DFS Traversal:
- For each vertex
uin the graph:- If
uhas not been visited, perform a DFS traversal starting fromu.
- If
- For each vertex
-
DFS Function (
visit(u)):- Mark
uas visited. - For each neighbor
vofu:- If
vhas not been visited, recursively callvisit(v).
- If
- After visiting all descendants of
u, adduto the front of the sorted list.
- Mark
-
Completion:
- The final list is a valid topological sort.
3.2. Implementation
function topologicalSortDFS(adj) {
const N = adj.length;
const visited = new Set();
const sortedOrder = [];
function visit(u) {
visited.add(u);
for (const v of adj[u]) {
if (!visited.has(v)) {
visit(v);
}
}
// All descendants visited, add u to the front
sortedOrder.unshift(u);
}
for (let i = 0; i < N; i++) {
if (!visited.has(i)) {
visit(i);
}
}
return sortedOrder;
}
4. Complexity Analysis
Both Kahn's algorithm and the DFS-based approach have the same complexity:
- Time Complexity:
O(N + M), whereNis the number of vertices andMis the number of edges. - Space Complexity:
O(N)for storing the in-degrees, the queue, and the sorted list.
Key Takeaway: Topological sort is essential for ordering tasks with dependencies in a DAG. Both Kahn's algorithm (using a queue and in-degrees) and the DFS-based approach (using recursion) can achieve this in linear time. The existence of a topological sort is also a proof that the graph is a DAG.
التالي · الدرس 69 من 92
Union-Find Operations and Data Structure
قراءة 3 دقيقة
أنهيت 68 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

