拓扑排序

liyao2025 · 2025-11-11 15:21:24 · 算法·理论

定义

拓扑排序 (Topological sorting) 要解决的问题是如何给一个有向无环图的所有节点排序。

Kahn 算法

过程

初始状态下，集合 S 装着所有入度为 0 的点，L 是一个空列表。每次从 S 中取出一个点 u （可以随便取）放入 L^` 然后将 u 的所有边 (u, v_1), (u, v_2), (u, v_3) \cdots 删除。对于边 (u, v)， 若将该边删除后点 v 的入度变为 0，则将 v 放入 S 中。

不断重复以上过程，直到集合 S 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 L，L 中顶点的顺序就是构造拓扑序列的结果。

时间复杂度

假设这个图 G = (V, E) 在初始化入度为 0 的集合 S 的时候就需要遍历整个图，并检查每一条边，因而有O(E+V) 的复杂度。然后对该集合进行操作，显然也是需要 O(E+V) 的时间复杂度。

因而总的时间复杂度就有 𝑂(𝐸 +𝑉)

例题

B3644 【模板】拓扑排序 / 家谱树 :::info[code_{my}] AC记录

#include <bits/stdc++.h>
using namespace std;
int n,a[10004],into[10004],t,vis[10004];
vector<int>edge[10004];
queue<int>q;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        while(cin>>t)
        {
            if(t==0)break;
            edge[i].push_back(t);
            into[t]++;
        }
    }
    for(int i=1;i<=n;i++)
        if(into[i]==0&&!vis[i])q.push(i),vis[i]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        cout<<u<<" ";
        for(int i=0;i<edge[u].size();i++)
        into[edge[u][i]]--;
        for(int i=1;i<=n;i++)
            if(into[i]==0&&!vis[i])q.push(i),vis[i]=1;
    }
    return 0;
}

:::