将 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 伪代码。