拓扑排序

拓扑排序

前提是有向无环图，是图的宽度优先搜索的应用

拓扑序列

若一个由图所有点构成的序列A满足，对于图的每条边(x,y)，x在A中的出现，都在y的前面，则称A是这个图的拓扑排序

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])//入度为零就加入队列
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}