1. 拓扑序
如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列就称为一个拓扑序。
获得一个拓扑序的过程就是拓扑排序。
AOV如果有合理的拓扑序，则必定是有向无环图。
每一次要输出的是没有前驱顶点的那个顶点。没有前驱顶点就是入度为0，也就是没有一个顶点指向他。在输出的同时，就是把这个顶点抹掉。
2. 算法流程
void TopSort(){
for(图中的每个顶点V){
// 如果顶点的入度为0，那么将这个节点存到队列中
if(Indegree[V] == 0)
Enqueue(V, Q);
}
while(!IsEmpty(Q)){
V = Dequeue(Q);
输出V，或者记录V的输出序号；cnt++;
// 遍历V的每个邻接点，并对他们的入度减1，如果入度为0，同样存到队列中
for(V的每个邻接点W)
if(--Indegree[W] == 0)
Enqueue(W, Q);
}
if(cnt != |V|)
ERROR("图中有回路");
}
这个算法还可以检测图是不是有向无环图
关键路径问题
哪些组是一天都不能耽误的，绝对不能延误的（没有机动时间的组）
问题1：整个工期有多长？
问题2： 哪几个组有机动时间？
从保证整个工期是18天，反推回去，看前面的节点最晚开始的时间。
机动时间的计算方式是：当前节点的最晚完成时间-上一节点的最早完成时间-两个节点之间的权重。
3. Leetcode 207. Course Schedule
https://leetcode.com/problems/course-schedule/
https://www.youtube.com/watch?v=fskPWs3Nuhc
step 1：把输出翻译成图的形式
用一个map来表示图。键为输出节点，值为图对应输出节点。
用一个vector来表示入度。
step2：获得一个拓扑序
- 把入度为0（没有先修课程要求的课程放到队列里），典型的bfs模板
-
把队列里的最先的节点取出来，，并且将节点的邻域节点的入度都减一。
-
如果邻域节点的入度减为0以后，那么这个节点就被push进队列。
- 依次类推。
- 最后遍历所有点的入度，如果存在入度不等于0（如果有环，那么入度为负数），那么说明有环，返回false
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 使用邻接链表的方式构造图
vector<int> input_node;
vector<vector<int>> graph(numCourses, input_node);
vector<int> indegree(numCourses, 0);
int in_, out_;
for(int i=0; i<prerequisites.size(); ++i){
in_ = prerequisites[i][1];
out_ = prerequisites[i][0];
indegree[out_] += 1;
graph[in_].push_back(out_);
}
// 把入度为0的节点存到队列中
queue<int> q;
for(int i=0; i<numCourses; ++i){
if(indegree[i] == 0)
q.push(i);
}
// 当队列不为空的时候，执行循环，取出入度为0的节点，并将邻接节点的入度减1
while(!q.empty()){
int zero_indegree = q.front();
q.pop();
int n = graph[zero_indegree].size();
for(int i=0; i<n; ++i){
int idx = graph[zero_indegree][i];
if(--indegree[idx] == 0)
q.push(idx);
}
}
// 如果存在入度不为0的节点，那么直接返回false
for(int i=0; i<numCourses; ++i){
if(indegree[i] != 0)
return false;
}
return true;
}
};
