Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

Kahn's Algorithm (Topological Sort)

Posted on Edited on In
Symbols count in article: 5.8k Reading time ≈ 5 mins.

DAG圖形結構中用BFS找合理順序

背景知識

圖，BFS, DFS走訪

理解問題

從課表問題建構圖，有向無環圖Directed Acyclic Graph (DAG) 走訪，有環回傳false/[]。

numCourses = 4
prerequisites = [[1,0], [2,0], [3,1], [3,2]] #[to, from]

  • 207.Course Schedule：回傳能否完成所有課程 True or False。
  • 210.Course Schedule II：回傳可以完成任何一種的課程順序，否則[]。

思路視覺化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0-> 1 or 2-> 3

207
1.建2個列表：courses：{course:prerequests}, pres：{prerequests:course}
1.找第一點(不在其他點後)
3.建一個queue, FIFO走訪，把所有下個節點的前提都刪除(1,2的0都刪除)
4.如果沒有前提再加入列表找下個節點(1,2加入queue)
ret count == numCourses

210
1.建2個列表：courses：{course:prerequests}, pres：{prerequests:course}
1.找第一點(不在其他點後)
3.建一個queue, FIFO走訪，把所有下個節點的前提都刪除(1,2的0都刪除)
4.如果沒有前提再加入列表找下個節點(1,2加入queue)
return ret if count==numCourses else []

Java

  • 207
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
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.*;
public class Solution {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses]; // prerequests count
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // construct prerequests count [2, 1, 1, 0]
        for(int[] pair:prerequisites){
            System.out.println(Arrays.toString(pair));
            indegree[pair[1]]++;
        }
        System.out.println(Arrays.toString(indegree));
        
        // find start point(no pre)
        for(int i=0;i<indegree.length;i++){
            if(indegree[i]==0) queue.add(i);
        }
        
        int select = 0;
        while(!queue.isEmpty()){
            numCourses--;
            int course = queue.poll(); // get head
            
            for(int[] pair:prerequisites){ // find next course
                if(pair[0]==course){
                    indegree[pair[1]]--;// remove previous course
                    if(indegree[pair[1]]==0){ // if no previous
                        queue.add(pair[1]); // append next course to find
                    }
                }
            }
        }
        return numCourses==0;
    }
    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1,0}, {2,0}, {3,1}, {3,2}};
        System.out.println(canFinish(numCourses,prerequisites));
    }
}
>
java -cp /tmp/ZzMu196mR2 Solution
[1, 0]
[2, 0]
[3, 1]
[3, 2]
[2, 1, 1, 0]
true
  • 210
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;
public class Solution {
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<Integer>[] map = new List[numCourses]; 
        Queue<Integer> queue = new LinkedList<Integer>();
        int[] result = new int[numCourses];
        int courseCount = numCourses;

        // {course:prerequests}
        for (int[] pair : prerequisites) {
            indegree[pair[0]]++;
            if (map[pair[1]] == null)
                map[pair[1]] = new ArrayList<>();
            map[pair[1]].add(pair[0]);
			// map[0, [1,2]] -> subject 0 is common prerequisite of subject[1,2]
        }
        System.out.println(Arrays.toString(map));

        // find start point(no pre)
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) queue.add(i);
        }
        System.out.println(queue);
        
        // travel stack
        while (!queue.isEmpty()) {
            int course = queue.poll(); // get head
            result[numCourses - courseCount] = course; // add to result array
            courseCount--;
            
			// check if we can study a new subject 
            if (map[course] == null) continue;

            for (int item : map[course]) {
                indegree[item]--;
                if (indegree[item] == 0)
                    queue.add(item);
            }
        }
		//  finish all subject,return path or [] 
        return courseCount == 0 ? result : new int[0];
    }
    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1,0}, {2,0}, {3,1}, {3,2}};
        System.out.println(Arrays.toString(findOrder(numCourses,prerequisites)));
    }
}
>
java -cp /tmp/ZzMu196mR2 Solution
[[1, 2], [3], [3], null]
[0]
[0, 1, 2, 3]

Python

  • 207 TC: O(E+V), SC: O(Vˆ2)
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
37
from collections import defaultdict, deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        # construct two-way table
        courses = defaultdict(set) # {course:prerequests}
        pres = defaultdict(set) # {prerequests:course}
        
        for course, pre in prerequisites:
            courses[course].add(pre)
            pres[pre].add(course)
        print("courses: ",courses) 
        print("pres: ",pres) 
        
        # find start point(no pre)
        queue = deque()
        for n in range(numCourses): # list all Courses
            if not courses[n]: # # append no pre, that's begin
              queue.append(n)
        
        # travel stack
        count = 0     
        while queue: # BFS
            cur = queue.popleft() # FIFO, pop是LIFO
            print(cur)
            count+=1
            for course in pres[cur]: # find next course
                courses[course].remove(cur) # remove previous course(don't use del)
                if not courses[course]:# if no previous 
                    queue.append(course) # append next course to find
                    
        return count == numCourses # can take all courses
        
print(canFinish(4, [[1,0], [2,0], [3,1], [3,2]]))

>
True
  • 210 TC: O(E+V), SC: O(Vˆ2)
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
37
38
39
40
41
from typing import List
from collections import defaultdict
from collections import deque

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        
        # construct two-way table
        courses = defaultdict(set) # {course:prerequests}
        pres = defaultdict(set) # {prerequests:course}
        
        for course, pre in prerequisites:
            courses[course].add(pre)
            pres[pre].add(course)
        print("courses: ",courses) 
        print("pres: ",pres) 
        
        # find start point(no pre)
        queue = deque()
        for n in range(numCourses): # list all Courses
            if not courses[n]: # append no pre, that's begin
              queue.append(n)
        
        # travel stack
        count,ret = 0, [] # 210  
        while queue:
            cur = queue.popleft() # FIFO, pop是LIFO
            print(cur)
            ret.append(cur) # 210
            count+=1
            
            for course in pres[cur]: # find next course
                courses[course].remove(cur) # remove previous course
                if not courses[course]: # if no previous
                    queue.append(course) # append next course to find
                    
        return ret if count==numCourses else [] # 210
        
print(findOrder(4, [[1,0], [2,0], [3,1], [3,2]]))

>
[0, 2, 1, 3] or [0, 1, 2, 3]

ref

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Welcome to my other publishing channels