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

2022-11-07 849 words 4 minutes

Contents

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.¹

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)

Below is the implementation of the above approach:

Examples

Course Schedule II

LeetCode 210. Course Schedule II²

It’s basically a slightly advanced version of Course Schedule in which you need to record the courses this time.

At the first I tried to approach this by DFS.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from collections import defaultdict

# DAG - topological sorting
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) # DFS
            stack.append(c0)

        visited = [False] * numCourses
        stack = []
        adj_keys = list(adj_lit.keys()) # to handle defaultdict's size changed during iteration in line-12
        for c0 in adj_keys:
            if not visited[c0]:
                traverse(c0)
        
        return stack
# Failed at task like:
#   n = 2
#   prerequisites = [[0,1],[1,0]]

But I quickly realized I’ve missed to handle the loop. Then I tried again.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
###### still failed at n=2, pre=[[0,1],[1,0]] ######  
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]:
                # detect loop (cycle)
                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]:
                # independent course
                if adj_list[c0] == []:
                    visited[c0] = True
                    output.append(c0)

                else:
                    DFS(c0, c0)
        return output    
###### still failed at n=2, pre=[[0,1],[1,0]] ######  

Still missing…

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import defaultdict, deque

class 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 Schedule³ [Medium]

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:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

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.