拓扑排序，但具有某种分组
看来这一定是一个常见的调度问题，但我没有看到解决方案，甚至没有看到该问题的名称。它就像拓扑排序，但不同......
给定一些依赖性，假设
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。所有歧义或不关心的内容都会被分组。
我认为诸如 拓扑排序与分组之类的算法将无法正确处理如下情况。
A -> B -> C -> D -> E
A - - - > M - - - > E
为此，算法应该返回
(A) -> (B, C, D, M) -> (E)
This
A -> B -> D -> F
A -> C -> E -> F
should return
(A) -> (B, D, C, E) -> (F)
While this
A -> B -> D -> F
A -> C -> E -> F
C -> D
B -> E
should return
(A) -> (B, C) -> (D, E) -> (F)
And this
A -> B -> D -> F
A -> C -> E -> F
A -> L -> M -> F
C -> D
C -> M
B -> E
B -> M
L -> D
L -> E
should return
(A) -> (B, C, L) -> (D, E, M) -> (F)
这个问题有名称和常规解决方案吗？ （带分组的拓扑排序中发布的算法是否可以正确处理此问题？）
编辑回答更多示例的请求：
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)
It seems this must be a common scheduling problem, but I don't see the solution or even what to call the problem. It's like a topological sort, but different....
Given some dependencies, say
A -> B -> D -- that is, A must come before B, which must come before D
A -> C -> D
there might be multiple solutions to a topological sort:
A, B, C, D
and A, C, B, D
are both solutions.
I need an algorithm that returns this:
(A) -> (B,C) -> (D)
That is, do A, then all of B and C, then you can do D. All the ambiguities or don't-cares are grouped.
I think algorithms such as those at Topological Sort with Grouping won't correctly handle cases like the following.
A -> B -> C -> D -> E
A - - - > M - - - > E
For this, the algorithm should return
(A) -> (B, C, D, M) -> (E)
This
A -> B -> D -> F
A -> C -> E -> F
should return
(A) -> (B, D, C, E) -> (F)
While this
A -> B -> D -> F
A -> C -> E -> F
C -> D
B -> E
should return
(A) -> (B, C) -> (D, E) -> (F)
And this
A -> B -> D -> F
A -> C -> E -> F
A -> L -> M -> F
C -> D
C -> M
B -> E
B -> M
L -> D
L -> E
should return
(A) -> (B, C, L) -> (D, E, M) -> (F)
Is there a name and a conventional solution to this problem? (And do the algorithms posted at Topological Sort with Grouping correctly handle this?)
Edit to answer requests for more examples:
A->B->C
A->C
should return
(A) -> (B) -> (C). That would be a straight topological sort.
And
A->B->D
A->C->D
A->D
should return
(A) -> (B, C) -> (D)
And
A->B->C
A->C
A->D
should return
(A) -> (B,C,D)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
令 G 为图的传递闭包。令 G' 为无向图，它是从 G 中删除方向并取补集而得到的。 G' 的连通分量就是您正在寻找的集合。
Let G be the transitive closure of the graph. Let G' be the undirected graph that results from removing the orientation from G and taking the complement. The connected components of the G' are the sets you are looking for.