DAG拓扑排序-Kahn算法

拓扑排序就是对一个有向无环图进行排序，使其变成一个线性关系，并且保证其前后的位置关系不改，简言之，就是把一个偏序变成一个全序(线性序)。

拓扑排序有两种算法，一种是借助DFS排序，另一种是卡恩算法，这里采用的是卡恩算法。

算法思想很简单就是，就是不断删除入度为零的节点，因为入度为零就说明该节点没有前去节点，所以可以加如我们最后所要求的序列中，而那些有前驱的节点，就要受限制，就不能加入我们的最后序列中。

所以算法的伪代码可以是这样:

存储图关系 a->b; //数组　二维向量都可以存储
in[b]++; //b的入度+1

for(int i = 0;i<n;i++){//扫描所有节点的入度
	if(in[i] == 0) q.push(i);//把入度为零的节点加入队列中
}

while(!q.empty()){
	int num = q.front();//取出队首元素
	ans.push_back(num);//加入最后答案中
	q.pop();

	for(int i = 0;i<v[i].size();i++){//所有被该节点指向的节点的入度-1
			if(--in[v[num][i]] == 0) q.push(v[num][i]);//如果某节点入度为零，该节点应该加入队列中
	}
}

输出最后答案;

需要注意的是：
１．构建图关系的时候，可能是正向建图，也可以是逆向建图,比如可以存储a > b ,也可以存储b < a,如果正向见图很复杂，可以考虑逆向见图。
２．存储图关系时最好采用二维vector，因为采用数组的话需要判断是否重复。
３．入度为零的点出队时候存在一个出队顺序问题，视具体情况而定,可以采用优先队列来控制出队顺序。

拓扑排序代码差不多可以这么写:

        vector <int > v;
        vector <int > a[MAX];
        queue <int > q;
        int n,m,x,y;
        cin >> n >> m;
        if(!n) break;
        
        int inn[n+10];
        memset(inn,0,sizeof(inn));
        
        for(int  i = 0;i<m;i++){
            cin >> x >> y;
            a[x].push_back(y);
            inn[y]++;
        }
        
        for(int i = 0;i<n;i++)
            if(!inn[i]){//入度为0的节点加入到队列中去
                q.push(i);
            }

        while(!q.empty()){
            int front = q.front();
            q.pop();
            v.push_back(front);
            for(int i = 0;i<(int)a[front].size();i++){
                if(--inn[a[front][i]] == 0)
                    q.push(a[front][i]);
            }
        }

最后是几道例题:
HDU 3342
HDU 1285
POJ 3687(加粗是有原因的)