拓扑排序是一个有向无环图的所有顶点的线性序列。

该序列需要满足每个顶点出现且只出现一次和如果有一条 A 到 B 的路径，在序列中 A 出现在 B 的前面。

拓扑排序可以判断有向图中是否有环，可以生成拓扑序列。

‌[卡恩算法]（Kahn算法）是一种用于解决有向无环图（DAG）的拓扑排序问题的算法。 它的主要思想是从图中选择入度为0的节点，将其加入结果列表中，并更新其余节点的入度。具体步骤如下：

• 初始化：遍历图中的所有顶点，计算每个顶点的入度，并将入度为0的顶点加入队列。
• 迭代处理：从队列中取出一个顶点，将其添加到结果列表中，然后更新其邻居节点的入度，如果某个邻居节点的入度变为0，则将其加入队列。
• 结束条件：如果队列为空，说明所有入度为0的节点都已被处理，此时检查是否所有节点都已加入结果列表，如果是，则拓扑排序完成；否则，说明图中存在环，无法进行拓扑排序。

卡恩算法的时间复杂度为O(V + E)，其中V是顶点数，E是边数，这是因为每个顶点都会被加入结果列表一次，且每条边都会被处理一次。‌

有向图的拓扑排序

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;
}