笔记: 拓扑排序

简介

拓扑排序（Topological Sorting）是图论中对有向无环图（DAG）中的顶点进行线性排序的一种方法,使得对于图中每一条有向边 $u \rightarrow v$,顶点 $u$ 都排在顶点 $v$ 的前面.

拓扑排序的本质是解决“先做什么、后做什么”的顺序问题,拓扑排序在生活中具有很多的应用场景,但在本文着重介绍在信息学竞赛中的运用

如何实现拓扑排序

前面的定义可能很抽象,但是如果只是为了竞赛只需要知道拓扑排序是怎么实现的能解决什么问题

拓扑排序本质上是寻找到一个入度为0的点,然后把这个顶点和出边都删掉并记录下这个顶点,重复循环直到没有顶点,剩下记录的数值按照先后排序就是拓扑排序了

这里有个优质的视频可视化地介绍了拓扑排序,但是没有将具体的算法实现(大概思路有的)
所以记得回来看我的文章

Kahn算法

Kahn算法的核心思想是

每次选择图中入度为 0 的节点，将其加入拓扑序列，并从图中删除它（同时减少所有邻接点的入度）。重复此过程，直到所有节点都被处理或发现图中有环。

变量一览

我们维护这些变量

使用邻接表可以较好的进行处理

算法步骤

算法步骤大概可以分4个阶段

1. 计算每个节点的入度

2. 将所有入度为 0 的节点入队

3. 循环处理队列：

   • 弹出队头节点，加入拓扑序列

   • 遍历该节点的出边，对每个邻接点 v 执行 ind[v]--

   • 若 ind[v] == 0，将其入队

4. 最终判断：

   • 如果拓扑序列中的节点数等于图中总节点数 → 成功排序

   • 否则 → 图中有环，无法拓扑排序

这种写法类似BFS

示例

来看个示例,假如是这个图(2指向3)

    0 → 1 → 3
     ↘     ↑
       2 →

g[0] = {1, 2}
g[1] = {3}
g[2] = {3}

ind[0] = 0
ind[1] = 1
ind[2] = 1
ind[3] = 2

参考执行过程

复杂度

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

因而总的时间复杂度就有 \( O(E + V) \)

空间复杂度 \( O(E + V) \)

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ind[10010];
vector<int> g[10010],res;
queue<int> q;

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        ind[v]++;
    }
    for(int i=0;i<n;i++)if(!ind[i])q.push(i);
    while(q.size()){
        int u=q.front();q.pop();
        res.push_back(u);
        for(int v:g[u]){
            if(--ind[v]==0)q.push(v);
        }
    }
    if(res.size()<n)puts("有环，无法拓扑排序");
    else for(int x:res)cout<<x<<' ';
}

或者你可以使用封装成函数的版本(不建议这样直接复制,多写一份代码多熟悉一点)

vector<int> topo(int n, vector<pair<int,int>>& e){
    vector<int> ind(n),g[n],res;
    for(auto [u,v]:e)g[u].push_back(v),ind[v]++;
    queue<int> q;
    for(int i=0;i<n;i++)if(!ind[i])q.push(i);
    while(q.size()){
        int u=q.front();q.pop();
        res.push_back(u);
        for(int v:g[u])if(--ind[v]==0)q.push(v);
    }
    return res.size()==n?res:vector<int>{};
}

调用示例

int main(){
    int n=4;
    vector<pair<int,int>> e={{0,1},{0,2},{1,3},{2,3}};
    auto r=topo(n,e);
    if(r.empty())puts("有环");
    else for(int x:r)cout<<x<<' ';
}

DFS写法

思路

在DFS中,当我们完成一个节点的所有子节点的遍历后,才将该节点加入到结果列表中.这个特性完美地符合拓扑排序的要求:一个节点必须出现在所有它依赖的节点(即其子孙节点)之前

为了防止重复访问和检测环路,我们通常会用一个状态数组来标记节点为“未访问”、“访问中”和“已访问”

具体执行有以下步骤

1.寻找任意一个未访问的节点,标记为访问中
2.对这个节点进行DFS,当一个DFS遍历完时,将该节点加入结果列表的最前面,同时把这个节点标记为已访问
3.重复执行,直到所有节点被访问
附加一个额外判断条件(不知道放哪) :如果遍历过程中发现一个“访问中”的节点,说明图中存在环

最关键的步骤是步骤2,因为DFS确保了当节点 $u$ 加入列表时,所有从它出发的路径上的节点都已经被处理并加入列表,所以 $u$ 一定会出现在这些节点之前

变量名一览

示例

假设有以下图

为了方便,我们高亮这三种状态

未访问 访问中 已访问

复杂度

$V,E$ 表示顶点数量和边数量

时间复杂度 \( O(E + V) \)

空间复杂度 \( O(E + V) \)

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5;
vector<int>g[MAXN],res;
int vis[MAXN];
bool has_cycle=0;

void dfs(int u){
  vis[u]=1;
  for(int v:g[u]){
    if(vis[v]==0)dfs(v);
    else if(vis[v]==1)has_cycle=1;
  }
  vis[u]=2;
  res.push_back(u);
}

int main(){
  int n=6;
  g[5]={2,0};//测试数据
  g[4]={0,1};
  g[2]={3};
  g[3]={1};

  for(int i=0;i<n;i++)if(vis[i]==0)dfs(i);
  if(has_cycle)cout<<"有环\n";
  else{
    reverse(res.begin(),res.end());
    for(int x:res)cout<<x<<" ";
  }
}

总结

如果没有要求两种写法都可以,复杂度都是一样的,我个人觉得Kahn算法较简单且容易理解

对比一下(GPT生成)

✅ 什么时候选 DFS？

• 更适合路径动态规划（如最长路径）等需先遍历所有依赖的场景；

• 可配合时间戳做深度分析；

• 适合静态图的分析（例如一次性加载，深度遍历所有后代）。

✅ 什么时候选 Kahn？

• 更适合用于在线处理、多次查询、任务调度系统等；

• 实现简单直观；

• 可以快速判断是否存在环，直接返回。

📌 总结一句话：

两者复杂度相同，选哪种取决于具体需求：

• 若关注“递归 + 动态规划”，用 DFS；

• 若重视“顺序构造 + 易实现”，用 Kahn。