本文介绍拓扑排序的原理和代码实现。

1 拓扑排序的基本原理

能够使用拓扑排序的图一定是一个有向无环图(DAG, Directed Acyclic Graph)。若是一个有向有环图，则任务无法完成，存在循环依赖问题。

2 拓扑排序的代码实现

2.1 使用深度优先遍历

2.2 使用广度优先遍历

2.3 课程表

课程表相关的LeetCode题目:
207. 课程表
210. 课程表 II
2050. 并行课程 III

2.3.1 207. 课程表

  1. 保存每个结点的入度数量；
  2. 保存每个结点的出度结点；
  3. 每次将入度为0的结点添加至队列，出队列时，将其关联的出度结点的入度减1；
  4. 当遍历完所有结点时，若存在入度不为0的结点，说明这个图存在环，任务无法完成；否则任务可以完成；

实际上该算法是用于判断这个有向图是否存在环。拓扑排序要求图为有向图无环。

 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

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses, 0);
        unordered_map<int, vector<int>> outdegreeNode;
        
        // init indegree and outdegreeNode
        for (int i = 0; i < prerequisites.size(); ++i) {
            int out = prerequisites[i][0];
            int in  = prerequisites[i][1];
            indegree[out]++;
            outdegreeNode[in].push_back(out);
        }

        queue<int> que;
        int count = numCourses; // node count
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                indegree[i] = -1;
                que.push(i);
                --count;
            }
        }

        while (!que.empty() && count != 0) {
            int front = que.front();
            que.pop();
            for (int item : outdegreeNode[front]) {
                if (indegree[item] > 0) {
                    --indegree[item];
                    if (indegree[item] == 0) {
                        indegree[item] = -1;
                        que.push(item);
                        --count;
                    }
                }
            }
        }

        return count == 0;
    }
};

2.3.2 210. 课程表 II

 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

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> indegree(numCourses, 0);
    unordered_map<int, vector<int>> outdegreeNode;
    
    // init indegree and outdegreeNode
    for (int i = 0; i < prerequisites.size(); ++i) {
        int out = prerequisites[i][0];
        int in  = prerequisites[i][1];
        indegree[out]++;
        outdegreeNode[in].push_back(out);
    }

    queue<int> que;
    int count = numCourses; // node count
    for (int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0) {
            indegree[i] = -1;
            que.push(i);
            --count;
        }
    }

    while (!que.empty() && count >= 0) {
        int front = que.front();
        que.pop();
        for (int item : outdegreeNode[front]) {
            if (indegree[item] > 0) {
                --indegree[item];
                if (indegree[item] == 0) {
                    indegree[item] = -1;
                    que.push(item);
                    --count;
                }
            }
        }
    }

    if (count == 0) {
        return res;
    }
    return {};
}

2.3.3 2050. 并行课程 III

 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

int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
    vector<int> indegree(n+1, 0);
    vector<int> indegreeMaxTime(n+1, 0); // 记录每个结点的入度结点中的最大值
    unordered_map<int, vector<int>> outdegreeNode;
    vector<int> node_time(time.begin(), time.end());
    
    // init indegree and outdegreeNode
    for (int i = 0; i < relations.size(); ++i) {
        int in = relations[i][0];
        int out  = relations[i][1];
        indegree[out]++;
        indegreeMaxTime[out] = max(indegreeMaxTime[out], node_time[in-1]);
        outdegreeNode[in].push_back(out);
    }

    queue<int> que;
    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == 0) {
            indegree[i] = -1;
            que.push(i);
        }
    }

    while (!que.empty()) {
        int front = que.front();
        que.pop();
        node_time[front-1] = indegreeMaxTime[front] + node_time[front-1];
        for (int item : outdegreeNode[front]) {
            if (indegree[item] > 0) {
                --indegree[item];
                indegreeMaxTime[item] = max(indegreeMaxTime[item], node_time[front-1]);
                if (indegree[item] == 0) {
                    indegree[item] = -1;
                    que.push(item);
                }
            }
        }
    }

    return *max_element(node_time.begin(), node_time.end());
}