有向无环图分阶段的拓扑排序
是否有一种算法，在给定一个未加权有向无环图的情况下，将所有节点排序到一组节点列表中，从而
- 保留拓扑顺序（即，对于所有边
u-
此问题是否有名称？
下图的可能排序是
[1], [2, 3], [4, 5], [6, 7]
另一个解决方案是
[1], [2, 3], [4], [5, 6, 7]
共有2个答案
如果没有前导节点，则将每个节点的阶段索引定义为零，或者将其前导节点的最大阶段索引加上一。将每个节点置于指定阶段。
可以按照拓扑顺序高效地评估阶段索引，使其成为您喜爱的拓扑排序算法的简单扩展。
考虑一下典型卡恩算法的这种变化：
-
< li >从包含所有没有传入边的节点的集合S0开始 < li >初始化下一组序列号1 < li >迭代Sn，对于每个节点N: < ol > < li >对于具有来自N的传入边的所有节点D，删除该边 < li >如果D没有其他传入边，则将其添加到Sn 1
S0的列表...Sk集合包含结果。
-
如何输出有向无环图的所有可能的拓扑排序？例如，给定一个图形，其中 V 指向 W 和 X，W 指向 Y 和 Z，X 指向 Z： 如何对此图进行拓扑排序以产生所有可能的结果？我能够使用广度优先搜索来获得V，W，X，Y，Z，并使用深度优先搜索来获得V，W，Y，Z，X。但无法输出任何其他种类。
-
我有一个任务类，它在执行前依赖于其他任务。我想将可以并行化的任务分组并排序。我决定它可以首先表示为DAG，并尝试使用JGrapht。首先，我遍历任务的输入列表，以获取所有具有依赖关系的任务，并将它们收集在一个列表中。然后，对于每个任务，我在图中创建一个顶点。 然后使用相同的列表，我试图创建节点之间的边。 然后我试着把任务分组 因此，结果是有序和分组的任务，例如图 结果将是 然而，当也是的前身时，它
-
问题内容： 好的，因此在根据输入数据进行拓扑排序时，通常存在多个正确的解决方案，可以根据这些正确的解决方案对图进行“处理”，以便所有依赖项都位于“依赖”它们的节点之前。但是，我正在寻找稍微不同的答案： 假设以下数据： 和（必须先于并且必须先于）。 只有这两个限制，我们有多种候选方案：（ ，， 等）。但是，我正在寻找一种将这些节点“分组”的方法，以便在处理完一组后，下一组中的所有条目都将处理其依赖项
-
问题：给定一个加权有向无环图（DAG）和其中的一个源顶点s，找出从s到给定图中所有其他顶点的最长距离。 请查找参考图：链接 为什么我们需要拓扑排序？我们不能简单地从源顶点使用修改后的BFS吗？为什么我们如此关心线性排序。 如果这是重复，请将我重定向到相关答案。 谢谢
-
Wikipedia以一种非常直观的方式(IMO)解释了依赖关系图，引用了当依赖于时，会产生边。换句话说，我们可以通过查看其邻接列表中可用的邻居立即找到任何给定节点的直接依赖关系（如果有的话）。 这似乎是实现依赖的一个明智的方法；它允许我们基本上像执行深度优先遍历（图中每个节点的DFS）一样容易地执行拓扑排序。如果节点表示“任务”，那么只有当任务的所有传递依赖项都已执行/访问时，我们才能执行/访问任
-
据我所知，如果您有一个现成的高效黑盒方法来处理强连接组件，那么进行拓扑排序的一种方法是： （假设-无自循环） null 我只想确保我正确理解事情。