Topological Sorting | LeetCode Course Schedule I/II | Graph, DFS, BFS

What’s Topological Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.1

Note: Topological Sorting for a graph is not possible if the graph is not a DAG. (i.e. If there is a loop/cycle in the Graph)

Examples

Course Schedule II

LeetCode 210. Course Schedule II2

It’s basically a slightly advanced version of Course Schedule in which .

At the first I tried to approach this by DFS.

from collections import defaultdict
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
if not prerequisites:
return list( range(numCourses) )
adj_lit = defaultdict(list)
for c0, c1 in prerequisites:
adj_lit[c0].append(c1)
def traverse(c0):
'''check a vertix's prerequisite'''
visited[c0] = True
for cs in adj_lit[c0]:
if not visited[cs]:
traverse(cs)
stack.append(c0)
visited = [False] * numCourses
stack = []
adj_keys = list(adj_lit.keys())
for c0 in adj_keys:
if not visited[c0]:
traverse(c0)

return stack


But I quickly realized I’ve . Then I tried again.


class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj_list = [[] for _ in range(numCourses)]
for c0, c1 in prerequisites:
adj_list[c0].append(c1)
def DFS(c0, master):
visited[c0] = True
for c1 in adj_list[c0]:

if adj_list[c1] == master:
acycle[0] = False
if not visited[c1]:
DFS(c1, master)

output.append(c0)

visited = [False] * numCourses
output = []
acycle = [True]
for c0 in range(numCourses):
if acycle[0] == False:
return []

if not visited[c0]:

if adj_list[c0] == []:
visited[c0] = True
output.append(c0)
else:
DFS(c0, c0)
return output

Still missing…

Then I adopted the solution from archit91 with BFS approach. It’s nicely structured and well-run.

Code

from collections import defaultdict, dequeclass Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = defaultdict(list)
in_degree = [0] * numCourses

for next_c, pre_c in prerequisites:
graph[pre_c].append(next_c)
in_degree[next_c] += 1

BFS_q = deque()
for cs in range(numCourses):
if in_degree[cs] == 0:
BFS_q.append(cs)

ans = []
while BFS_q:
curr = BFS_q.popleft()
ans.append(curr)
for next_c in graph[curr]:
in_degree[next_c] -= 1
if in_degree[next_c] == 0:
BFS_q.append(next_c)

return ans if len(ans)==numCourses else []

Course Schedule

LeetCode 207. Course Schedule3

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.

Example 1:

Example 2:

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Thinking

This is basically the simpler version of Course Schedule II.

Code

from collections import defaultdict, dequeclass Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
pre_cs_list = [0] * numCourses
for next_c, pre_c in prerequisites:
graph[pre_c].append(next_c)
pre_cs_list[next_c] += 1

q = deque()

for i in range(numCourses):
if pre_cs_list[i] == 0:
q.append(i)
ans = []
while q:
curr = q.popleft()
ans.append(curr)
for next_c in graph[curr]: pre_cs_list[next_c] -= 1
if pre_cs_list[next_c] == 0:
q.append(next_c)
return len(ans) == numCourses

Related FAQ in The Discussion

range() vs xrange() in Python — GeeksforGeeks

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store