Promoted
Promoted

Course Schedule using Topological Sort

Topic: Algorithms

Topological Sort is an algorithm derived from Depth-First-Search(DFS). Topological Sort resolves the dependency network and works in acyclic directed graphs. It is also used in detecting cycles in directed graphs. In problems like loading packages, one needs to resolve dependent packages and load them first. Topological Sort helps in resolving dependent packages. Similar problems can be also solved like traversing and creating hierarchy, finding order, etc.

Template for Topological Sort

0heading
  • Before understanding Topological Sort, make sure you understand DFS.
  • In the given example below, we load package ‘a’ in the system. We see ‘a’ has dependency packages ‘b’ , ‘c’ and ‘d’. ‘c’ is dependent on ‘d’.
  • So we need to load packages in order as ‘d’, ‘c’, ‘b’ and then ‘a’.
  • Here we will use recursive DFS and stack.
  • We run DFS on every node
  • If the node has no dependency or if the dependent of nodes are already in stack then we add that node to stack
  • Below is the python code.
1list
Dependency graph.
2image
import collections def TopologicalSort(nodes): edges = collections.defaultdict(set) for u, v in nodes: edges[u].add(v) def dfs(vertex, visited, stack): visited.add(vertex) #mark node visited for u in edges.get(vertex, {}): #check unvisited connected nodes if u not in visited: dfs(u, visited, stack) #if all connected node visited, add the current node to stack stack.append(vertex) stack = [] #to store resolved nodes visited = set() for vertex in edges.keys(): if vertex not in visited: dfs(vertex, visited, stack) return stack #['d', 'c', 'b', 'a']
3code

Course Schedule(Cycle Detection)

4heading

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false

6paragraph
Promoted
Promoted
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3]..
7image

Intuition

8subheading
  • This problem asks to check if there is any cycle in the graph.
  • We don't need a stack here because we don’t need to return results. Instead, we return False if there is a cycle.
  • Here we need to check three conditions - 1. If node visited, 2. If node partially visited 3. Node visited
  • Instead of using a HashSet, we will use a hashmap to store node status in the visited hashmap.
  • In DFS, if we found any node partially visited, which means we found a cycle.
  • If the node is marked as visited, we return True because we have met the dependency.
  • If the node is uninvited we call DFS.
9list
def canFinish(numCourses, prerequisites): #if no dependecy True if not prerequisites: return True def dfs(vertex,visited): #vertex dependecy met. if visited[vertex] == 2: return True #case 2: visiting visited[vertex] = 1 for v in edges.get(vertex, {}): #case 3: visited if (visited[v] == 2): continue elif (visited[v] == 1): return False else: #case 1: unvisited node if not dfs(v,visited): return False #we resolved dependecy visited[vertex] = 2 return True edges = collections.defaultdict(set) for u, v in prerequisites: edges[u].add(v) visited = {v:0 for v in range(numCourses)} for v in range(numCourses): if not dfs(v,visited): return False return True
10code

Course Schedule II (Find Order)

11heading

IThere are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

13paragraph
Promoted
Promoted
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
14code
Find Order.
15image

Intuition

16subheading
  • Here we use the same solution from the above problem but since we need a return order. We use a stack.
  • We use a stack similar to the template above
17list
def findOrder(numCourses, prerequisites): #if no dependecy all course in any order if not prerequisites: return [u for u in range(numCourses)] def dfs(vertex,visited,stack): #vertex dependecy met. if visited[vertex] == 2: return True #case 2: visiting visited[vertex] = 1 for v in edges.get(vertex, {}): #case 3: visited if (visited[v] == 2): continue elif (visited[v] == 1): return False else: #case 1: unvisited node if not dfs(v,visited,stack): return False #we resolved dependecy visited[vertex] = 2 stack.append(vertex) return True edges = collections.defaultdict(set) for u, v in prerequisites: edges[u].add(v) stack = [] visited = {v:0 for v in range(numCourses)} for v in range(numCourses): if not dfs(v,visited,stack): return [] return stack
18code