拓扑排序

应用
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列。

有向无环图(DAG)
拓扑排序是基于有向无环图而言的

Directed Acyclic Graph,如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图。

拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑序列。

顶点活动网(AOV)

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。

• 在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列
• 由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。
• AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

c++实现

1. 构建 邻接表 和 入度数组， 入度为0的 节点入队，
2. 取队首节点，访问该节点的输出，将它可到达顶点的 入度减1 ， 如果某个顶点的入度减为0，则将它加入队列
3. 重复进行2步，直到队列为空(没有入度为0的顶点了，即已经访问了所有可达的节点)， 如果队列为空时 入过队的节点为N(图节点全部访问过),说明拓扑排序成功， 否则，拓扑排序失败，图存在环

代码对应 leetcode: 207. 课程表

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        map<int,set<int>> adjcent;  // 邻接表
        vector<int> indegree(numCourses,0);  // 入度数组

        for(auto edge:prerequisites){
            adjcent[edge[0]].insert(edge[1]);
            indegree[edge[1]] ++;
        } 

        queue<int> mq;
        int cnt = 0;
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) mq.push(i);
        }

        while(!mq.empty()){
            int pre = mq.front();
            mq.pop();
            cnt+=1;
            auto adjs = adjcent[pre];

            for(auto adj:adjs){
                indegree[adj]--;
                if(indegree[adj]==0) mq.push(adj);
            }
        }
        return cnt==numCourses;
    }
};