拓扑排序

概述

拓扑排序是图论中的一种重要算法，用于对有向无环图（DAG）进行排序。在拓扑排序中，图中的节点被排序，使得如果图中存在一条从节点 A 到节点 B 的有向路径，那么在排序结果中，节点 A 出现在节点 B 之前。

拓扑排序常用于解决一些实际问题，例如任务调度、依赖关系分析等。在项目管理中，如果任务之间存在先后顺序的依赖关系，那么可以利用拓扑排序确定任务的执行顺序，以保证任务能够按照依赖关系的要求顺利完成。

思想

拓扑排序算法的基本思想是通过不断移除入度为零的节点，并更新相应节点的入度信息，直至所有节点都被排序完成。

1. 初始化：首先，对图中的每个节点计算其入度（即指向该节点的边的数量），并将入度为零的节点加入一个待处理队列中。
2. 迭代处理：从待处理队列中选择一个入度为零的节点，将其加入排序结果中，并将该节点从图中移除（即删除与其相连的所有边）。同时，更新与被移除节点相连的节点的入度信息。
3. 重复步骤 2，直至待处理队列为空。

如果最终排序结果中包含了图中的所有节点，则拓扑排序成功；否则，说明图中存在环路，无法进行拓扑排序。

拓扑排序算法的时间复杂度取决于图的大小和边的数量，通常为 $O(V+E)$，其中 V 是节点的数量，E 是边的数量。

算法模板

纯净版

▶

代码

vector<int> h[N];
vector<int> d(n + 1, 0);
vector<int> ans;
auto topsort = [&]() -> void
{
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!d[i])
            q.push(i);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        ans.push_back(t);
        for (auto el : h[t])
        {
            if( -- d[el] == 0)
            q.push(el);
        }
    }
};

带注释版

▶

代码

vector<int> h[N];//vector存图
vector<int> d(n + 1, 0);//入度数量
vector<int> ans;//答案数组
auto topsort = [&]() -> void
{
    queue<int> q;//队列
    for (int i = 1; i <= n; ++i)//把所有入度为0的点加进来
        if (!d[i])
            q.push(i);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        ans.push_back(t);
        for (auto el : h[t])
        {
            if( -- d[el] == 0)//更新度数并且判断是否入度为0，为0即可push进队列
            q.push(el);
        }
    }
};