Loading... # 引入 离散教材上讲过关键路径。其中，在求最长路径时，第一步是对节点进行“重新标号”。经过查阅，发现这个步骤其实叫做“拓扑排序”。很容易知道，如果一个图可以拓扑排序，那个它是有向无环图（DAG, Directed Acyclic Graph），从而它可能是一个能反映事件先后依赖关系的PT图（Potentialtask Graph）。 # 问题 (1) [LeetCode #207](https://leetcode-cn.com/problems/course-schedule/) “能完成学习”说明给的图是DAG。用拓扑排序判断给定图是否是DAG图即可。即如果还有节点没有标号时，图中就找不到入度为0的点了，那么就不是DAG。反之，能顺利给所有点标号，就是DAG。 (2) [LeetCode #210](https://leetcode-cn.com/problems/course-schedule-ii/) 本题其实就是在1的基础上，把拓扑排序的结果输出出来。 (3) [LeetCode #1203](https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/) 本题要求每个小组的工作排在一起。其实，这是一个双重（嵌套）拓扑排序的结构。可以先将每个组的工作“打包”构建整个小组之间的PT图（先后关系）进行拓扑排序，然后对每个组内的工作再进行拓扑排序。 # 实现 (1) 本题有两点实现上的技巧。 一开始实现的时候比较愚笨地把给的边列表转换成了邻接矩阵。但其实本题用邻接表（adjacency list）在空间和时间上都更优。因为，在删除一个点，需要知道它的直接后继时，用邻接表可以直接遍历这个点的后继列表，而邻接矩阵需要遍历所有的点并用if判断。同时，为了避免不断地盲目扫描全部节点来获取入度为0的点，应该借助一个队列。一开始，把所有入度为0的点加入队列。由于每个点的入度变化是每次删除一个点时可能减1，也就是新产生的入度为0的点一定是删除某个点时它的入度从1变成0，因此一边删除点，就可以一边把新的入度为0的点加入队列。队列空了之后，判断是否删除了所有点即可。 LeetCode的输入数据往往给的是边列表。从此题可以看出，边列表有时应转换成邻接矩阵，有时应转换成邻接表。（说不定有时也可以直接使用。） ```cpp class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<int> pre_num(numCourses, 0); vector< vector<int> > adjacency(numCourses); for (auto iter : prerequisites) { // iter[1] -> iter[0] pre_num[ iter[0] ]++; adjacency[ iter[1] ].push_back(iter[0]); } queue<int> q; for (int i = 0; i < numCourses; i++) { if (pre_num[i] == 0) q.push(i); } int n = numCourses; while (!q.empty()) { int node_to_del = q.front(); q.pop(); n--; for (auto iter : adjacency[node_to_del]) { pre_num[iter]--; if (pre_num[iter] == 0) q.push(iter); } } return n == 0; } }; ``` (2) 对1略加改造即可。 ```cpp class Solution { public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<int> order; vector< vector<int> > adjacency(numCourses); vector<int> pre_num(numCourses, 0); for (auto iter : prerequisites) { // iter[1] -> iter[0] adjacency[ iter[1] ].push_back(iter[0]); pre_num[ iter[0] ]++; } queue<int> q; for (int i = 0; i < numCourses; i++) { if (pre_num[i] == 0) q.push(i); } while (!q.empty()) { int node_to_del = -1; node_to_del = q.front(); q.pop(); order.push_back(node_to_del); for (auto iter : adjacency[node_to_del]) { // node_to_del -> iter pre_num[iter]--; if (pre_num[iter] == 0) q.push(iter); } } if (order.size() == numCourses) return order; else return vector<int>(0); } }; ``` Last modification：June 25th, 2020 at 09:04 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 Appreciate the author