将 DAG 拓扑排序为批次

Question

我正在寻找一种算法将 DAG 排序为顶点批次，使得批次中的任何顶点之间都没有边，并且批次按顺序排序，使得批次中的任何顶点都没有边缘到按排序顺序在其后面的批次。我似乎无法对通用拓扑排序进行有效的修改，因为要发现将顶点放入哪个批次，您必须在其所属批次之前填充所有批次。有效：

batches = []
while vertices:
    batch = []
    for v in vertices.copy():
        for v' in v.edges:
            if v' in vertices:
                break
        else:
            batch.append(v)
            vertices.remove(v)
    batches.append(batch)

但是，该算法

O(n^2)

适用于反向排序的“线性”图以及用于顶点查找的哈希表。

对于 pythonic 伪代码感到抱歉。

Answer 1

我写了

batching-toposort

来为我自己的项目之一解决这个问题。它是Kahn算法的修改版，具有以下性能特征：

• V 任务顶点和 E 依赖边的时间复杂度 O(|V| + |E|)
• 空间复杂度 O(|V|)

核心算法伪代码如下：

given G = adjacency list of tasks and dependents (~O(1) lookup):

let N = map from tasks to in-degree counts (~O(1) lookup / update)
let L = [] (empty output list) (~O(1) append)
let R1 = list of root tasks (~O(1) addition, ~O(n) iteration)

while R1 is nonempty
    append R1 to L
    let R2 = [] (empty list for next batch) (~O(1) append)
    for each task T in R1
        for each dependent D of T (as per G)
            decrement in-degree count for D (in N)
            if D's in-degree (as per N) is 0
                add D to R2
    R1 = R2

return L