学步园

书上讲得太抽象，下面博客写的很清晰明了

http://blog.csdn.net/acceptedxukai/article/details/6959882

拓扑排序简单来说就是把一个图的所有节点排序,使得每一条有向边(u,v)对应的u都排在v的前面。 

拓扑排序最大的用途就是判断一个有向图是否有环，当然判断还有一种方法就是Floyd算法。

如果用邻接表的话拓扑排序的时间复杂度是O(N*E)，邻接矩阵是O（N^2），N表示顶点数，E表示边数，Floyd时间复杂度是O(N^3)。

性质
1、 拓扑排序在有向无环图中才能排出有效的序列，否则能判断该有向图有环。
2、如果输入的有向图中的点,不存在入度为0的点,则该有向图存在回路
3、如果存在的入度为0的点大于一个,则该有向图肯定不存在一个可以确定的拓扑序列但并不妨碍拓扑排序 

下面给出核心程序：

vector<int>g[N];//邻接表存储
int vis[N],topo[N],cnt;

bool dfs(int u)
{
    vis[u] = -1;//-1用来表示顶点u正在访问
    for(int i = 0 ; i < g[u].size() ; i ++)
    {
        if(vis[g[u][i]] == -1)//表示这个点进入了两次，肯定出现了环
            return false;
        else if(vis[g[u][i]] == 0)
        {
            dfs(g[u][i]);
        }
    }
    vis[u] = 1;
    topo[cnt++] = u;//放到结果数组里，输出的时候记得倒序输出，（回溯的原因）
    return true;
}

bool toposort(int n)
{
    memset(vis,0,sizeof(vis));
    for(int i = 1 ; i <= n ; i ++)
    {
        if(!vis[i])
        {
            if(!dfs(i)) return false;//huan
        }
    }
    return true;
}

还可以判断是否有环