algorithm - 拓扑排序，但具有某种分组

Question

看来这一定是一个常见的调度问题，但我没有看到解决方案，甚至没有看到该问题的名称。有点像拓扑排序，但又不同....

给定一些依赖关系，比如说

A -> B -> D -- that is, A must come before B, which must come before D
A -> C -> D

拓扑排序可能有多种解法:

    A, B, C, D
and A, C, B, D

都是解决方案。

我需要一个返回这个的算法:

(A) -> (B,C) -> (D)

也就是说，做A，然后做所有的B和C，然后你可以做D。所有不明确或无关紧要的都分组。

我认为算法如 Topological Sort with Grouping 中的算法将无法正确处理以下情况。

A -> B -> C -> D -> E
A - - - > M - - - > E

为此，算法应该返回

(A) -> (B, C, D, M) -> (E)

这个

A -> B -> D -> F
A -> C -> E -> F

应该返回

(A) -> (B, D, C, E) -> (F)

虽然这

A -> B -> D -> F
A -> C -> E -> F
     C -> D
     B -> E

应该返回

(A) -> (B, C) -> (D, E) -> (F)    

还有这个

A -> B -> D -> F
A -> C -> E -> F
A -> L -> M -> F
     C -> D
     C -> M
     B -> E
     B -> M
     L -> D
     L -> E

应该返回

(A) -> (B, C, L) -> (D, E, M) -> (F)    

这个问题有名称和常规解决方案吗？ (在 Topological Sort with Grouping 上发布的算法是否正确处理了这个问题？)

编辑以回答更多示例的请求:

A->B->C
A->C 

应该返回

(A) -> (B) -> (C). That would be a straight topological sort.

和

A->B->D
A->C->D
A->D

应该返回

(A) -> (B, C) -> (D)

和

A->B->C
A->C
A->D

应该返回

(A) -> (B,C,D)

Answer 1

令 G 为图的传递闭包。设 G' 是无向图，它是从 G 中去除方向并取补得到的。 G' 的连通分量就是您要查找的集合。