Topology Sort
Definition: For Directed Acyclic Graph(DAG), topology sorting is a linear ordering of vertices such that for every directed edge u->v, vertex u comes before node v in the ordering.
Algorithm
- Use DFS and a temporary stack, every time visiting a node, we don't print it but firstly recursively call all its adjacent vertices then push the node into stack;
- A node is in the stack only when all its adjacent nodes are already in the stack;
- Use a HashSet or boolean array to track if one element is already visited;
Take following graph for demonstration:
In this graph, a path
1.Assume start from Node 2, marke Node 2 as visited
and traverse its child node;
stack: [empty]
set: [2]
2.Visiting Node 3, and traverse to its child node;
stack: [empty]
set [2, 3]
3.Visiting Node 1, since Node 1 has no child, push
Node 1 into stack. Backtracking to Node 3 and
Node 1 sequentially, push them into stack;
stack: [1, 3, 2]
set: [2, 3, 1]
4.Pick another unvisited node from the graph, assume
it's Node 4, and keep visited its child node;
stack: [1, 3, 2]
set: [2, 3, 1, 4]
5.Visiting Node 0, since Node 0 has no child, push
Node 0 into stack and backtrack to Node 4. Since
Node 4 has other child, keep visiting its child;
stack: [1, 3, 2, 0]
set: [2, 3, 1, 4, 0]
6.Attempt to visit Node 1, since it's already visited,
backtrack to Node 4. Since all its children have
already been visited, push Node 4 into stack;
stack: [1, 3, 2, 0, 4]
set: [2, 3, 1, 4, 0]
7.Currently, we leave one node unvisited. Visiting
Node 5. Since all its children have already been
visited, push Node 5 into stack;
stack: [1, 3, 2, 0, 4, 5]
set: [2, 3, 1, 4, 0, 5]
8.One topology sort sequence is just the pop-order
sequence of the stack: [5, 4, 0, 2, 3, 1]
LeetCode 210. Course Schedule II
Analysis:
- This is a typical topology sort problem. Every prerequisite [i, j] means in order to take course i, you firstly have to take course j. So the directed path of the graph should be like
- Before we start to traverse the courses, we need to construct the graph first. We can use adjacent list to represent the graph since the number of courses is presented and they're all represented by integer starting from 0;
- Besides, since it's possible that there's no correct order(when cycle occurs in graph), we also need to determine if a cycle occurs in the graph along with sort the sequence;
Code:
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses < 2) {
return new int[] {0};
}
ArrayList<Integer>[] adjList = new ArrayList[numCourses];
for (int i = 0; i < adjList.length; ++i) {
adjList[i] = new ArrayList<Integer>();
}
for (int[] prerequisite : prerequisites) {
adjList[prerequisite[1]].add(prerequisite[0]);
}
boolean[] visited = new boolean[adjList.length];
HashSet<Integer> set = new HashSet<>();
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < adjList.length; ++i) {
if (dfs(adjList, i, visited, set, stack)) {
return new int[0];
}
}
int[] result = new int[numCourses];
int count = 0;
while (stack.size() > 0) {
result[count++] = stack.pop();
}
for (int i : result) {
System.out.println(i);
}
return result;
}
// Return value: True -> contains circle
private boolean dfs(ArrayList<Integer>[] adjList, int course, boolean[] visited, HashSet<Integer> set, Stack<Integer> stack) {
if (visited[course]) {
return true;
}
if (set.contains(course)) {
return false;
}
visited[course] = true;
set.add(course);
for (int i : adjList[course]) {
if (dfs(adjList, i, visited, set, stack)) {
return true;
}
}
visited[course] = false;
stack.push(course);
return false;
}
Job Schedule
Problem: Given a list of jobs, some of the jobs have to be finished in order. For example, given jobs [A, B, C, D] and A can only be finished after B and C are finished, B can only be finished after D is finished. Please provide a sequence representing a correct order to schedule the jobs.
Analysis:
- Similar as previous problem, we can use Topology Sort to solve this problem;
- We use a HashMap instead of adjacent list to represent the graph since there's no specific indexing order for the jobs;
Since the input only provides jobs and their prerequisite jobs, we need to keep the reverse relationship in our map. Based on the example mentioned in problem, the map contents should be like following:
Map Contents: A : empty B : A C : A D : B
class Pair {
String name;
String[] preNames;
public Pair(String parent, String[] children) {
this.name = parent;
this.preNames = children;
}
}
public String[] jobSchedule(List<String> jobs, List<Pair> pairs) {
if (jobs == null || jobs.size() == 0) {
return new String[0];
}
HashMap<String, ArrayList<String>> map = new HashMap();
for (String job : jobs) {
map.put(job, new ArrayList<String>());
}
for (Pair pair : pairs) {
for (String parent : pair.preNames) {
map.get(parent).add(pair.name);
}
}
HashSet<String> set = new HashSet();
Stack<String> stack = new Stack();
for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) {
dfs(map, entry.getKey(), set, stack);
}
String[] result = new String[stack.size()];
int count = 0;
while (stack.size() > 0) {
result[count++] = stack.pop();
System.out.println(result[count - 1]);
}
return result;
}
private void dfs(HashMap<String, ArrayList<String>> map, String job, HashSet<String> set, Stack<String> stack) {
if (set.contains(job)) {
return;
}
set.add(job);
for (String child : map.get(job)) {
dfs(map, child, set, stack);
}
stack.push(job);
}