Topological Sort
Category: Famous Algorithms
```
Problem Statement
Topological Sort You're given a list of arbitrary jobs that need to be completed; these jobs are represented by distinct integers. You're also given a list of dependencies. A dependency is represented as a pair of jobs where the rst job is a prerequisite of the second one. In other words, the second job depends on the rst one; it can only be completed once the rst job is completed. Write a function that takes in a list of jobs and a list of dependencies and returns a list containing a valid order in which the given jobs can be completed. If no such order exists, the function should return an empty array. Sample Input jobs = [1, 2, 3, 4] deps = [[1, 2], [1, 3], [3, 2], [4, 2], [4, 3]] Sample Output [1, 4, 3, 2] or [4, 1, 3, 2] Hints Hint 1 Try representing the jobs and dependencies as a graph, where each vertex is a job and each edge is a dependency. How can you traverse this graph to topologically sort the list of jobs? Hint 2 One approach to solving this problem is to traverse the graph mentioned in Hint #1 using Depth-rst Search. Starting at a random job, traverse its prerequisite jobs in Depth-rst Search fashion until you reach a job with no prerequisites; such a job can safely be appended to the nal order. Once you've traversed and added all prerequisites of a job to the nal order, you can append the job in question to the order. This approach will have to track whether nodes have been traversed already, whether they're in the process of being traversed (which would indicate a cycle in the graph and therefore no valid topological order), or whether they're ready to be traversed. Hint 3 Another approach to solving this problem is to traverse the graph mentioned in Hint #1 starting specically with jobs that have no prerequisites. Keep track of all the jobs that have no prerequisites, traverse them one by one, and append them to the nal order. For all of these jobs, remove their dependencies from the graph and update the number of prerequisites for each of these dependencies accordingly (these dependencies should now have one prerequisite less since one of their prerequisite job has just been added to the nal order). As you update the number of prerequisites for these other jobs, keep track of the ones that no longer have prerequisites and that are ready to be traversed. You'll eventually go through all of the jobs if there are no cycles in the graph. If there is a cycle in the graph, there will still be jobs with prerequisites and you'll know that there is no valid topological order. This approach will involve keeping track of the number of prerequisites per job as well as all the actual dependencies of each job. Optimal Space & Time Complexity O(j + d) time | O(j + d) space - where j is the number of jobs and d is the number of dependencies
```
Approach & Solution
Solution 1
```
Solution 1 Solution 2
orderedJobs.add(node.job);
removeDeps(node, nodesWithNoPrereqs);
}
boolean graphHasEdges = false;
for (JobNode node : graph.nodes) {
if (node.numOfPrereqs > 0) {
graphHasEdges = true;
}
}
return graphHasEdges ? new ArrayList
Solution 2
```
Solution 1 Solution 2
2
3 import java.util.*;
4
5 class Program {
6 // O(j + d) time | O(j + d) space
7 public static List
Solution 3
```
Solution 1 Solution 2
while (nodes.size() > 0) {
JobNode node = nodes.get(nodes.size() - 1);
nodes.remove(nodes.size() - 1);
boolean containsCycle = depthFirstTraverse(node, orderedJobs);
if (containsCycle) return new ArrayList
Solution 4
```
Solution 1 Solution 2
2
3 import java.util.*;
4
5 class Program {
6 // O(j + d) time | O(j + d) space
7 public static List
```
Test Cases
``` Test Case 1 {"jobs": [1, 2, 3, 4], "deps": [[1, 2], [1, 3], [3, 2], [4, 2], [4, 3]]} Test Case 2 { "jobs": [1, 2, 3, 4, 5, 6, 7, 8], "deps": [ [3, 1], [8, 1], [8, 7], [5, 7], [5, 2], [1, 4], [1, 6], [1, 2], [7, 6] ] } Test Case 3 { "jobs": [1, 2, 3, 4, 5, 6, 7, 8], "deps": [ [3, 1], [8, 1], [8, 7], [5, 7], [5, 2], [1, 4], [6, 7], [1, 2], [7, 6] ] } Test Case 4 { "jobs": [1, 2, 3, 4, 5, 6, 7, 8], "deps": [ [3, 1], [8, 1], [8, 7], [5, 7], [5, 2], [1, 4], [1, 6], [1, 2], [7, 6], [4, 6], [6, 2], [2, 3] ] } Test Case 5 { "jobs": [1, 2, 3, 4, 5, 6, 7, 8], "deps": [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 1]] } Test Case 6 { "jobs": [1, 2, 3, 4, 5, 6, 7, 8, 9], "deps": [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [7, 6], [7, 8], [8, 1]] } Test Case 7 { "jobs": [1, 2, 3, 4, 5, 6, 7, 8], "deps": [[1, 2], [3, 5], [4, 6], [3, 6], [1, 7], [7, 8], [1, 8], [2, 8]] } Test Case 8 { "jobs": [1, 2, 3, 4, 5, 6, 7, 8], "deps": [ [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 8], [3, 8], [4, 8], [5, 8], [6, 8], [7, 8] ] } Test Case 9 { "jobs": [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], "deps": [ [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 8], [3, 8], [4, 8], [5, 8], [6, 8], [7, 8], [2, 3], [2, 4], [5, 4], [7, 6], [6, 2], [6, 3], [6, 5], [5, 9], [9, 8], [8, 0], [4, 0], [5, 0], [9, 0], [2, 0], [3, 9], [3, 10], [10, 11], [11, 12], [2, 12] ] } Test Case 10 { "jobs": [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], "deps": [ [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 8], [3, 8], [4, 8], [5, 8], [6, 8], [7, 8], [2, 3], [2, 4], [5, 4], [7, 6], [6, 2], [6, 3], [6, 5], [5, 9], [9, 8], [8, 0], [4, 0], [5, 0], [9, 0], [2, 0], [3, 9], [3, 10], [10, 11], [11, 12], [12, 2] ] } Test Case 11 {"jobs": [1, 2, 3, 4, 5], "deps": []} Test Case 12 {"jobs": [1, 2, 3, 4, 5], "deps": [[1, 4], [5, 2]]}