图算法整理（三）：拓扑排序

Posted on | Edited on | In |

有些算法，自己觉得也就是那么回事，特别简单，但是想清楚每个细节怎么做，有什么小技巧，把它快速的实现出来，并不是那么容易。从想法到实现，总是有差距的。

经典问题：Course Schedule

LeetCode 207. Course Schedule
https://leetcode.com/problems/course-schedule/description/

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

1
2
3
4
Input: 2, [[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:

1
2
3
4
5
Input: 2, [[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.

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
calculate inDegree # 入度，有多少边到当前结点
queue q
counter = 0 # 用于最后检查是不是所有的点都visited
for each v with inDegree[v] == 0:
    q.push(v)
while !q.empty():
    v = q.pop()
    counter++
    for each w adjacent v:
        inDegree[v]-- # 关键！当一个点visit之后，减小所有其指向点的入度
        if inDegree[v] == 0:
            q.push(v)
check counter == vertexNum

C++实现

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
class Solution {
public:
    bool canFinish(int N, vector<pair<int, int>>& P) {
        vector<vector<bool>> g(N, vector<bool>(N, false));
        for (auto p : P) {
            g[p.first][p.second] = true;
        }
        queue<int> q;
        vector<int> inDegree(N, 0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (g[j][i] == true) {
                    inDegree[i]++;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            if (inDegree[i] == 0)
                q.push(i);
        }
        int num = 0;
        while (!q.empty()) {
            int t = q.front();
            q.pop();
            num++;
            for (int i = 0; i < N; i++) {
                if (g[t][i]) {
                    inDegree[i]--;
                    if (inDegree[i] == 0)
                        q.push(i);
                }
            }
        }
        return num == N;
    }
};

DFS

TODO..