拓扑排序

Algorithm

May 25, 2023

是解决有前置课程限制的课表安排之类的问题，用有向边代表一个事件和它的前置事件，那么这样构成的有向图的拓扑排序（结果并不唯一）就是一个规划方案。

拓扑排序的对图的要求是有向无环图（Directed Acyclic Graph，DAG），可以使用一个基于 DFS 的拓扑排序的方法，可以在线性时间里进行拓扑排序，并且能够检查环的存在。

这个基于 DFS 的线性的拓扑排序的算法很可能也是来源于 Tarjan¹，基本思路和前面介绍的TarjanDFS也是类似，关注边的回溯情况，非常简单，直接看实现。

思路

区别于前面为每个点维护 $\text{index}$ 和 $\text{lowpt}$，来求解寻找强连通分量，拓扑排序只需要检测环是否存在，因此可以简化为一个三元值，指示点的未访问、访问中和访问结束三个状态，如果 DFS 过程中遇到了一个访问中的点，那么一定存在环。

对于拓扑排序本身，按照 DFS 过程中，在所有出边访问结束后把当前点加入向量中，这就得到了一个拓扑排序的一个逆序结果，最后再把向量逆序回来，就得到了最终结果

实现

源代码

数据结构

#[repr(u8)]
#[derive(Default, Clone, Copy, PartialEq, Eq)]
enum DFSMeta {
    #[default]
    Green,
    Yellow,
    Red,
}
use DFSMeta::*;

整体过程

pub fn toposort_tarjan(g: &Graph) -> Result<Vec<usize>, (usize, usize)> {
    let mut ans = Vec::new();

    let max_v = g.vertexs().max().unwrap();

    let mut vertexs = vec![DFSMeta::default(); max_v + 1];

    for u in g.vertexs() {
        if vertexs[u] == Green {
            dfs(g, u, &mut vertexs, &mut ans)?;
        }
    }

    ans.reverse();

    Ok(ans)
}

DFS子过程

fn dfs(
    g: &Graph,
    u: usize,
    vertexs: &mut Vec<DFSMeta>,
    ans: &mut Vec<usize>,
) -> Result<(), (usize, usize)> {
    vertexs[u] = Yellow;

    for v in get!(g.e => u => vec![]) {
        match vertexs[v] {
            Green => {
                dfs(g, v, vertexs, ans)?;
            }
            Yellow => {
                return Err((u, v)); // found edge on cycle
            }
            Red => (), // just skip
        }
    }

    vertexs[u] = Red;
    ans.push(u);

    Ok(())
}

注解

Edge-disjoint spanning trees and depth-first search RE Tarjan Acta Informatica 6 (2), 171-185 ↩