Skip to content

拓扑排序

2021-03-26

简介

给出 n 个元素的 m 组关系:a>b,a>c,b>c,b>d,,试将 n 个元素按大小排序。

将上述关系转化为有向图,ab 代表 a>b。这种反映节点大小关系的图称作 AOV 网。

拓扑排序求的是符合条件的优先顺序,即拓扑序列。

原理

根据定义,没被箭头指着的节点(即入度为 0 的节点)是当前最大的节点。

节点 a 的入度为 0。在拓扑序列中追加 a,并删除 a 和它的所有邻边。 拓扑序列:a

故样例的一种拓扑序列为 a,e,b,c,d,f

INFO

同一张 AOV 网可能有多个拓扑序列。

  1. 定义一个队列,用于存放节点;
  2. 将所有入度为 0 的节点入队;
  3. 取出队头的节点,并删除它的所有出边.若出现入度为零的节点,将其入队。

拓扑排序结束时,若拓扑序列未包含全部节点,则剩下的节点形成了闭环。此时不存在拓扑序列。

时间复杂度为 O(n+m)

cpp
const int N = 1e6;
int n, deg[N];    // deg[u]: u 的入度
vector<int> g[N]; // g[u]: u 的邻接点集合
vector<int> vec;  // vec: 拓扑序列

// 预处理所有节点的入度
void pre() {
    memset(deg, 0, sizeof deg);
    for (int u = 1; u <= n; u ++)
        for (int v : g[u])
            deg[v] ++;
}

void topSort() {
    pre();
    vec.clear();
    for (int i = 1; i <= n; i ++)
        if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vec.push_back(u);
        for (int v : g[u])
            if (! -- deg[v]) // 出现新的节点入度为 0
                q.push(v);
    }
    if (vec.size() != n) // 不存在拓扑序列
        vec.clear();
}