Teaching Kids Programming – Topological Sort Algorithm on Directed Graphs (Course Schedule, BFS)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional integer list courses representing an adjacency list where courses[i] is the list of prerequisite courses needed to take course i.

Return whether it’s possible to take all courses.

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix.
Example 1
Input
courses = 0 –> 1 –> 2
Output
True
Explanation
We can take course 1, then course 0, and then course 2

---

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.

Hints:
This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

Topological Sort Algorithm on Directed Graphs – via BFS

The Topological sorting gives an order that we can visit the vertices in a directed graphs where the prerequisite vertices need to be visited first. A prerequisite or dependency is a edge with direction. We can first start with all nodes that have zero indegree (meaning no edges coming to them) – and then we can decrement the indegree of all out nodes as we deque a current vertex. Once a out node has become zero indegree, we can visit it – thus pushing to the queue.

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

class Node(object):
    def __init__(self):
        self.inDegrees = 0
        self.outNodes = []
 
class Solution:
    def solve(self, courses):
        graph = defaultdict(Node)
        totalDeps = 0
        for i, v in enumerate(courses):
            for j in v:
                graph[i].outNodes.append(j)
                graph[j].inDegrees += 1
                totalDeps += 1
        q = deque()
        for a, node in graph.items():
            if node.inDegrees == 0:
                q.append(a)
        r = 0
        while q:
            v = q.popleft()
            for a in graph[v].outNodes:
                graph[a].inDegrees -= 1                
                r += 1
                if graph[a].inDegrees == 0:
                    q.append(a)
        return r == totalDeps

class Node(object):
    def __init__(self):
        self.inDegrees = 0
        self.outNodes = []

class Solution:
    def solve(self, courses):
        graph = defaultdict(Node)
        totalDeps = 0
        for i, v in enumerate(courses):
            for j in v:
                graph[i].outNodes.append(j)
                graph[j].inDegrees += 1
                totalDeps += 1
        q = deque()
        for a, node in graph.items():
            if node.inDegrees == 0:
                q.append(a)
        r = 0
        while q:
            v = q.popleft()
            for a in graph[v].outNodes:
                graph[a].inDegrees -= 1                
                r += 1
                if graph[a].inDegrees == 0:
                    q.append(a)
        return r == totalDeps

The time complexity is O(V+E) where V is the number of vertices and E is the number of edges.

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

class Node(object):
    def __init__(self):
        self.inDegrees = 0
        self.outNodes = []
 
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        G = defaultdict(Node)
        
        total = 0
        for a, b in prerequisites:
            G[a].inDegrees += 1
            G[b].outNodes.append(a)
            total += 1
            
        q = deque()
        for a, node in G.items():
            if node.inDegrees == 0:
                q.append(a)
                
        r = 0
        while q:
            v = q.popleft()
            for a in G[v].outNodes:
                G[a].inDegrees -= 1
                r += 1
                if G[a].inDegrees == 0:
                    q.append(a)
                    
        return r == total

class Node(object):
    def __init__(self):
        self.inDegrees = 0
        self.outNodes = []

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        G = defaultdict(Node)
        
        total = 0
        for a, b in prerequisites:
            G[a].inDegrees += 1
            G[b].outNodes.append(a)
            total += 1
            
        q = deque()
        for a, node in G.items():
            if node.inDegrees == 0:
                q.append(a)
                
        r = 0
        while q:
            v = q.popleft()
            for a in G[v].outNodes:
                G[a].inDegrees -= 1
                r += 1
                if G[a].inDegrees == 0:
                    q.append(a)
                    
        return r == total

When the queue is exited (the BFS terminates), if the number of indegrees we decrement is not equal to the number of edges, thus there is a Cycle in the Graph – hence we cannot visit all the nodes.

–EOF (The Ultimate Computing & Technology Blog) —