Topological Sort Pattern
What is Topological Sort?
Topological Sort is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.
In simpler terms, it's an ordering of vertices that respects the dependencies between them.
When to Use Topological Sort
Topological Sort is useful when:
- You need to schedule tasks with dependencies
- You need to find the order of compilation for files with dependencies
- You need to determine the order of courses with prerequisites
- You need to resolve dependencies in a build system
DFS-based Topological Sort
Here's an implementation of topological sort using DFS:
Important Properties
- DAG Requirement: Topological sort is only possible for directed acyclic graphs (DAGs). If the graph has a cycle, there is no valid topological ordering.
- Non-uniqueness: A graph can have multiple valid topological orderings.
- Source and Sink: A source is a vertex with no incoming edges, and a sink is a vertex with no outgoing edges. In a topological ordering, sources come first and sinks come last.
Time and Space Complexity
Time Complexity:
O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity:
O(V), where V is the number of vertices in the graph, for storing the visited set and the stack.
Application: Course Schedule II
A common application of topological sort is the Course Schedule II problem, where we need to find the order in which to take courses given their prerequisites.
Pattern 3: Topological Sort
Learn how to use DFS to order vertices in a directed acyclic graph such that for every directed edge (u, v), vertex u comes before v.
What is Topological Sort?
Topological Sort is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.
In simpler terms, it's an ordering of vertices that respects the dependencies between them.
Example:
Graph:
A → C
B → C → E → F → G
B → D → F
E → H
Topological Order: B, A, D, C, E, F, G, H
Explanation: This ordering ensures that for every directed edge (u, v), vertex u comes before vertex v. For example, B comes before C and D, C comes before E, and so on.
When to Use Topological Sort
Task Scheduling
When you have a set of tasks with dependencies (some tasks must be completed before others), topological sort can help you find a valid order to execute the tasks.
Course Prerequisites
When planning a course schedule where some courses have prerequisites, topological sort can help you find a valid order to take the courses.
Build Systems
In build systems, where some files depend on others, topological sort can help determine the order in which to compile the files.
The DFS-based Topological Sort Algorithm
1Initialize
Initialize a visited set and a stack to store the topological order.
2Start DFS
For each unvisited vertex, start DFS from it. This handles disconnected graphs.
3Recursive DFS
Recursively visit all unvisited neighbors of the current vertex.
4Post-order Push
After visiting all neighbors, push the current vertex to the stack. Finally, reverse the stack to get the topological order.
Implementation
Here's an implementation of topological sort using DFS:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647function topologicalSort(graph) { // Set to keep track of visited vertices const visited = new Set(); // Stack to store the topological order const stack = []; // Visit all vertices for (const vertex in graph) { if (!visited.has(vertex)) { dfs(graph, vertex, visited, stack); } } // Reverse the stack to get the topological order return stack.reverse();} function dfs(graph, vertex, visited, stack) { // Mark the vertex as visited visited.add(vertex); // Visit all neighbors for (const neighbor of graph[vertex]) { if (!visited.has(neighbor)) { dfs(graph, neighbor, visited, stack); } } // After visiting all neighbors, push the vertex to the stack stack.push(vertex);} // Example usage:const graph = { 'A': ['C'], 'B': ['C', 'D'], 'C': ['E'], 'D': ['F'], 'E': ['F', 'H'], 'F': ['G'], 'G': [], 'H': []}; const order = topologicalSort(graph);console.log(order); // Output: ['B', 'A', 'D', 'C', 'E', 'F', 'G', 'H']How it works: We use DFS to explore the graph, but instead of processing a vertex when we first visit it, we process it after we've explored all its neighbors. This ensures that a vertex is processed only after all vertices that depend on it have been processed. Finally, we reverse the order to get the topological sort.
Important Properties
DAG Requirement
Topological sort is only possible for directed acyclic graphs (DAGs). If the graph has a cycle, there is no valid topological ordering because it would create a circular dependency.
Non-uniqueness
A graph can have multiple valid topological orderings. For example, if there are two vertices with no dependencies on each other, they can appear in any order in the topological sort.
Source and Sink
A source is a vertex with no incoming edges, and a sink is a vertex with no outgoing edges. In a topological ordering, sources come first and sinks come last.
Time and Space Complexity
Time Complexity
O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Explanation: We visit each vertex once (O(V)) and explore each edge once (O(E)). Even though we run DFS multiple times, each vertex and edge is processed exactly once across all DFS calls.
Space Complexity
O(V), where V is the number of vertices in the graph.
Explanation: We need to store the visited set (O(V)) and the stack for the topological order (O(V)). Additionally, the recursion stack in DFS can grow to size V in the worst case. Overall, the space complexity is O(V).
Application: Course Schedule II
A common application of topological sort is the Course Schedule II problem, where we need to find the order in which to take courses given their prerequisites.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859function findOrder(numCourses, prerequisites) { // Build the adjacency list representation of the graph const graph = Array(numCourses).fill().map(() => []); for (const [course, prereq] of prerequisites) { graph[prereq].push(course); } // 0 = not visited, 1 = visiting (in recursion stack), 2 = visited const visited = Array(numCourses).fill(0); // Stack to store the topological order const stack = []; // Check for cycles and build the topological order for (let i = 0; i < numCourses; i++) { if (visited[i] === 0 && hasCycle(graph, i, visited, stack)) { return []; // Return empty array if there's a cycle } } // Reverse the stack to get the topological order return stack.reverse();} function hasCycle(graph, vertex, visited, stack) { // Mark the vertex as visiting visited[vertex] = 1; // Visit all neighbors for (const neighbor of graph[vertex]) { // If the neighbor is not visited, check if there's a cycle in the subtree if (visited[neighbor] === 0) { if (hasCycle(graph, neighbor, visited, stack)) { return true; } } // If the neighbor is in the recursion stack, a cycle is found else if (visited[neighbor] === 1) { return true; } } // Mark the vertex as visited visited[vertex] = 2; // After visiting all neighbors, push the vertex to the stack stack.push(vertex); // No cycle found in this subtree return false;} // Example usage:const numCourses = 4;const prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]; const order = findOrder(numCourses, prerequisites);console.log(order); // Output: [0, 1, 2, 3]How it works: We build a directed graph where an edge from course A to course B means B is a prerequisite for A. Then we perform a topological sort on the graph to find a valid order to take the courses. If there's a cycle in the graph, it means there's a circular dependency among courses, making it impossible to find a valid order.