拓扑排序

EchoHua0402 · 2023-03-12 14:22:57 · 算法·理论

算法——拓扑排序

概念

在图论中，拓扑排序(Topological Sorting)是一个有向无环图(DAG)的所有顶点的线性序列。

序列必须满足这两个条件：

1. 每个顶点出现且仅出现一次
2. 若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面
3. 只有有向无环图(DAG)才有拓扑序

例：

有向无环图G：

拓扑序为：

求解拓扑序

拓扑排序大多都用BFS求解

将E点加入到序列中

有向连通图G为空，输出序列

拓扑排序的应用场景

拓扑排序通常用来排序具有依赖关系的事物

例如用一个DAG图表示一个食物链，其中每个顶点表示食物链中的一个动物，用有向边表示会被吃的生物A和会吃A的生物B。在这个食物链中，任意两个动物不是具有确定的关系，就是没有关系，即满足生物学的要求，不会出现环。

献上拓扑排序模板

void Topological_Sorting()
{
    while (!q.empty())//队列非空(在执行函数前要把所有入度为0的顶点都push进来)
    {
        int u=q.front();//取出队首
        q.pop();
        for (int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];//从u到v有一条有向边
            in[v]--;//v的入度-1
            if (!in[v])//若点v的入度为0则push到队列中
            {
                q.push(v);
            }
        }
    }
}