算法学习之路|拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。（来自百度百科定义）

如果你学过离散数学就不难理解这定义，如果没学过可能就没法理解，建议先去补补偏序/全序的概念，本篇不会多谈这些理论概念性的东西，想要了解请自行百度。
接下来说下拓扑排序的算法实现：

拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
废话不多说上代码(用的是c++stl实现的)

vector<int> G[MAXN];  // 邻接表。  
int son[MAXN];          // 入度数。  
void topo(){ 
    queue<int> que; 
    int ok = 0; 
    for (int i = 0; i < n; i++) 
        if (!son[i]) 
            que.push(i);    // 入度为0时入队。  
    while (!que.empty()){ 
        if (que.size() > 1) 
            ok = 1;         // 当队列中个数超多1时，表示有不唯一解。  
        int t = que.front(); 
        que.pop(); 
        cnt--;          //  如果队列为空后，计数器> 0， 说明存在环结构。  
        for (int i = 0; i < G[t].size(); i++) 
            if (--son[G[t][i]] == 0) // 判断减掉当前点的关系后，点的入度是否为0。  
                que.push(G[t][i]); 
    } 
}