拓扑排序

发表于 | 分类于 | 浏览 次

拓扑排序是将有向五环图G所有的顶点排成一个线性序列，使得对图G中的任意两个顶点u，v，如果存在边u->v，那么在序列中u一定在v前面。这个序列又称为拓扑序列。

拓扑排序可以用来判断图中是否有环，另一种用来判断图中是否有环的数据结构是并查集。

求拓扑排序算法步骤：

  1. 定义一个队列Q，并把所有入度为0的节点加入队列加入队列。
  2. 取队首节点，输出。然后删去所有从它出发的边，并令这些边到达的顶点的入度减1。如果某个顶点的入度减去0，则将其加入队列。
  3. 反复进行第二步操作，直到队列为空。如果队列为空时入过队的节点数目恰好为N，说明拓扑排序成功，则图G为有向无环图；否则，拓扑排序失败，图G中有环。

207. Course Schedule

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.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

解法1：拓扑排序

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if(numCourses <= 0){
            return true;
        }
        vector<int> inDegree(numCourses, 0);
        
        // 统计每个节点的入度
        for(vector<int> vec : prerequisites){
            ++inDegree[vec[0]];
        }
        
        queue<int> q;
        
        // 将入度为0的节点加入到队列中
        for(int i=0;i<numCourses;++i){
            if(inDegree[i] == 0){
                q.push(i);
            }
        }
        
        vector<int> res;
        while(!q.empty()){
            // 每次取出队列首的节点（入度为0）
            int num = q.front();
            res.push_back(num);
            q.pop();
            
            // 更新从该节点出去的边的尾节点的入度
            for(auto vec: prerequisites){
                if(vec[1] == num){
                    if(--inDegree[vec[0]] == 0){
                        q.push(vec[0]);
                    }
                }
            }
        }
        return numCourses == res.size();
    }
};

解法2：深度优先遍历

参考文献

[1]https://www.liwei.party/2019/02/16/leetcode-tag/topological-sort/