拓扑排序
拓扑排序理论
拓扑排序（Topological sorting）解决的问题是对有向无环图的所有的节点排序，要求任意两个存在依赖关系的节点，被依赖的节点都必须在另一个节点前面。
拓扑排序的顺序并不唯一，除了排序也可以用于判断有向图中是否存在环。
实现
通常使用Kahn算法解决，其核心在于入度为0的节点就一定没有被依赖。
主要思路如下：
-
建图，同时记录每个节点入度。
-
遍历每个节点的入度，将入度为0的节点全部入队。
-
取出队头，遍历它的所有出边，将出边终点的入度-1，并放进结果数组
-
如果某个终点的入度减至0，则入队。
-
检查是否所有节点都放入了结果数组
-
如果全部放入，则该数组的顺序就是其中一种拓扑排序
- 如果没有，则该图中存在环或不连通。
拓扑排序输出的序列不唯一，如果有顺序的要求，可以用优先队列替换队列
例题
拓扑排序
题目链接：210. 课程表 II - 力扣（LeetCode）
点击展开题目
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
- 例如，想要学习课程
0，你需要先完成课程1，我们用一个匹配来表示：[0,1]。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != bi- 所有
[ai, bi]互不相同
实现代码
点击展开代码
class Solution {
public:
//拓扑排序
//建图，int du[]存入度
//初始化后遍历入度，把入度为0的点全部压进队列
//问队列top的出度，存top并将所有top出度节点的入度-1，如果某个节点减到0了也压进队列，直到队列空
//统计已经问过的点，没问完就不能拓扑排序，问完了则输出
//统计：开等同点数的数组，初始化为-1，问完以后检查最后一个点是否是-1。
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> du(numCourses,0);
vector<vector<int>> graph(numCourses);
queue<int> que;
vector<int> res(numCourses,-1);
//建图
for(auto point:prerequisites){
graph[point[1]].push_back(point[0]);
du[point[0]]+=1;
}
//初始化
if(!que.empty())que.pop();
for(int i=0;i<numCourses;i++){
if(du[i]==0)que.push(i);
}
//轮询
int idx=0;
while(!que.empty()){
int curr=que.front();
res[idx++]=curr;
que.pop();
for(auto i:graph[curr]){
du[i]-=1;
if(du[i]==0)que.push(i);
}
}
//输出
if(res[numCourses-1]==-1)return vector<int>();
else return res;
}
};
反向建图
题目链接：码蹄集OJ-事务处理
思路
该题必须用反向建图的原因是，使用小根堆拓扑排序只能选定下一步可选节点中优先度最高的节点，如果高优先度的节点位于一条较长的事件链尾部，就难以按正确的优先顺序进行排序。
考虑反向建图，对于约束[i,j]（需要先完成事件i才能进行事件j），建图时记为j->i，则每个节点的入度表示完成该节点才能进行的节点的数量。
AOE网
AOE网（Activity of edge Network）是特殊的有向无环图，有且仅有一个入度为0的起点和一个出度为0的终点，需要解决对于一组存在依赖关系的事件，某个特定事件允许的最早和最晚发生时间，常应用于分模块进行的工程。