拓扑排序 Topo

zifuneko · 2025-11-18 22:04:10 · 算法·理论

定义

拓扑排序（Topological sorting）是在 DAG（有向无环图） 中对其顶点的一种线性排序，使得对于从顶点 {\displaystyle u} 到顶点 {\displaystyle v} 的每个有向边 {\displaystyle u\to v}，{\displaystyle u} 在排序中都在 {\displaystyle v} 之前。

这就像是在给一系列有 依赖关系 的任务进行排序。比如“穿裙子”这个任务，依赖于“先穿内衣”。那么拓扑排序的结果中，“穿内衣”必然在“穿裙子”之前。

Kahn

非常直观的算法。模拟了一个“不断移除没有前置依赖的节点”的过程。

算法步骤：

1. 初始化：

   • 计算图中每个节点的入度（即有多少条边指向它）；

   • 创建一个队列，将所有入度为 0 的节点加入其中。这些节点是“起点”，它们不依赖于任何其他任务；

   • 初始化一个空列表，用于存放拓扑排序的结果。

2. 循环处理：

   • 从队列中取出一个节点 u，并将其加入结果列表；

   • 遍历 u 的所有指向的节点 v；

   • 将 v 的入度减 1；

   • 如果此时 v 的入度变为 0，说明 v 的所有前置依赖都已被满足，则将 v 加入队列；

   • 重复此过程，直到队列为空。

3. 结束检查：

   • 如果结果列表中的节点个数与图中总节点数相同，说明排序成功，返回该列表。

   • 如果结果列表中的节点个数少于总节点数，说明图中存在环，无法进行拓扑排序。

B3644 【模板】拓扑排序 / 家谱树

代码实现

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

const int MAX = 105;
queue<int> q;
vector<int> g[MAX], ans;
int rd[MAX], n;

void kahn()
{
    for(int i=1; i<=n; i++)
        if(rd[i] == 0) q.push(i);
    while(!q.empty())
    {
        int t = q.front(); q.pop();
        ans.push_back(t);
        for(auto v : g[t])
        {
            rd[v]--;
            if(rd[v] == 0) q.push(v);
        }
    }
    if(ans.size() != n) cout << "有环" << endl;
    else for(auto v : ans) cout << v << ' ';
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int a; cin >> a;
        while(a) {g[i].push_back(a), rd[a]++; cin >> a;}
    }
    kahn();
    return 0;
}

DFS

利用深度优先搜索，在回溯时记录节点，本质上是一种后序遍历。

算法步骤：

1. 对图中的每个未访问节点执行DFS。

2. 在DFS过程中：

   • 递归地访问它所有指向的节点。

   • 当某个节点的所有邻居都处理完毕后，将该节点压入一个栈。

3. 最终，栈顶到栈底（或列表从头到尾）的顺序就是一个拓扑排序。

代码实现（未检测环）

#include<bits/stdc++.h>
using namespace std;
const int MAX = 105;
vector<int> e[MAX];
int n, vis[MAX];

stack<int> ans;
void dfs(int u)
{
    for(auto v : e[u]) {if(vis[v]) continue; dfs(v);}
    vis[u] = 1; ans.push(u);
}

signed main()
{
    int n, a; cin >> n;
    for(int i=1; i<=n; i++)
        while(cin >> a && a)
            e[i].push_back(a);
    for(int i=1; i<=n; i++) if(!vis[i]) dfs(i);
    while(!ans.empty()) cout << ans.top() << ' ', ans.pop(); 
    return 0;
}

解析：

1. 先递归处理所有后继节点（依赖当前节点的节点）

2. 当所有后继节点都处理完后，再处理当前节点

3. 使用栈来保证"依赖关系"的正确性

总结