有向无环图

有向无环图（Directed Acycilc Graph, DAG）：从任意顶点出发都无法回到自身的有向图。

拓扑排序

定义

任一两个顶点u,v间，如果存在边u->v，则排序后u一定在v前面。

问题导入

上图表示了数学课程间的相互关系，图的每个结点表示一门课程，每条有向边u->v表示“u是v的先导课程”（即上完u才能上v）的关系。

不难发现，如果要把上面所有课程排成课程顺序，保证在学习一门课程时，它的先导课程都已经全部学完，如果两门课程之间没有先导关系则排序任意。那么这一过程就可以抽象为拓扑排序。拓扑排序的序列不唯一。

注意： 很显然，拓扑排序只有在有向无环图中才能成功。如果图中有环，就不可能满足拓扑排序的定义，比如在上例中，数学分析是计算方法的先导，计算方法是高等几何的先导，但如果高等几何又是数学分析的先导，那整个课程不就乱套了。

算法实现

过程抽象：不断抽出入度为0的结点

1. 定义一个队列Q，把所有入度为0的结点全部入队
2. 取出队首结点，输出。 然后删去从它出发的所边， 并令这些边达到的顶点的入度减1。 如果某个顶点入度变为0，则入队。
3. 重复2操作，直到队列为空。 队列为空时，若如果队的结点恰好为顶点数N，说明拓扑排序成功；否则，拓扑排序失败，图中有环。

代码实现

#include
#include   //用stl库中的queue实现队列
#include
using namespace std;
const int MAXV = 100;
vector G[MAXV];    //邻接表实现图G
int n,m,inDegree[MAXV];//顶点数，入度
//拓扑排序
bool topologicalSort(){
    int num = 0;
    queue q;
    for(int i = 0; i