遍历有向图广度优先，具有最长路径的顶点优先

Question

给定一个有向依赖图，我想从根节点开始逐层遍历该图（即广度优先），但是按照特定顺序获取每个层上的节点。在我的例子中，每个级别上的节点顺序必须按照它们的深度排序，首先是最深的节点。

简单示例：

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

从节点 A 开始，我希望遍历给我顺序 A、B、C（而不是 A、C、B，因为 B 下有 C）。没有循环。

非常感谢任何提示。我是优秀的 JGraphT 库的新手，所以可能忽略了一些简单的解决方案。

解决此问题的一种方法是：

1. 查找从根 (A) 开始的所有路径
2. 根据长度对路径进行排序（最高的在前）
3. 对于每条路径遍历节点并将节点放在列表中的正确位置。
4. 正确的位置是通过在列表中未找到新节点的第一个位置对列表进行线性搜索来确定的

但也许已经有一些内置算法，所以我不必对上面的代码进行编码？ :-)

Answer 1

听起来你可以简单地使用 topological sort of your graph. In jgrapht you can accomplish this with the TopologicalOrderIterator