拓扑排序

定义

在有向无环图（DAG）中，求一遍历序列，使得存在边$u \rightarrow v$时，$u$在序列中出现在$v$之前。

性质

• 若图中存在环，则不存在拓扑排序。
• 拓扑排序不一定唯一
• 存在拓扑排序$\leftrightarrow$该图是DAG。

Kahn算法（BFS）

步骤

1. 选择一个入度为0的节点
2. 删除该节点和所有以它为起点的边
3. 重复步骤1和步骤2，直到所有节点都被删除

代码

以邻接表为例

// 邻接表
vector<vector<int>> adj; 
vector<int> kahn(int n){
    // 初始化入度
    vector<int> indeg(n, 0);
    for(int i = 0;i < n;i++)
        for(int v: adj[i]) 
            indeg[v]++;
    // 入度为0的节点队列
    queue<int> q;
    for(int i = 0;i < n;i++)
        if(!indeg[i]) 
            q.emplace(i);
    // BFS
    vector<int> res;
    while(!q.empty()){
        // 取出入度为0的节点u
        int u = q.front();
        q.pop();
        res.emplace_back(u);
        // 删除以u为起点的边
        for(int v: adj[u]){
            indeg[v]--;
            if(!indeg[v]) q.emplace(v);
        }
    }
    // 没有全部删除完说明有环
    if(n != res.size()) return {};
    return res;
}

扩展

• 字典序最小的拓扑排序，改用优先队列
• 拓扑排序是否唯一，看队列里是否元素数量$\gt 1$

DFS算法

步骤

1. 后序dfs遍历图，访问所有后继节点后入栈
2. 对未访问节点进行1操作，直到所有节点都被访问
3. 反转栈，得到拓扑排序

代码

以邻接表为例

// 邻接表
vector<vector<int>> adj; 
// 记录访问状态（-1：访问完成，0：未访问，1：正在访问）
vector<int> vis;
bool dfs(int u, vector<int>& st){
    vis[u] = 1;
    for(int v: adj[u]){
        // 正在访问的节点再次出现，说明有环
        if(vis[v] == 1) return false;
        // 未访问的节点递归访问，有环直接返回
        if(!vis[v] && !dfs(v)) return false;
    }
    // 所有后继访问完，标记并入栈
    vis[u] = -1;
    st.emplace_back(u);
    return true;
}

vector<int> topo_sort(int n){
    // 初始化访问状态
    vis.assign(n, 0);
    // 对每个节点进行dfs
    vector<int> st;
    for(int i = 0;i < n;i++)
        // 未访问的节点递归访问，有环直接返回
        if(!vis[i] && !dfs(i, st)) return {};
    // 反转栈，得到拓扑排序
    reverse(st.begin(), st.end());
    return st;
}

应用

DP on DAG

• 先求出拓扑排序
• 用拓扑序做状态转移