基于递归依赖创建森林

Creating a forest based on recursive dependencies

我有一个场景，其中箭头左侧的每个项目都是源项目，右侧是从属项目。评估源的方法我需要先评估依赖项。

我想为每个父项创建从源到依赖项的映射并标识叶子。依赖项需要从单个输入 (A -> B , C ) 开始构建，当依赖项不依赖于任何它意味着它是叶时。我怎样才能递归地构建它？任何指针都会有所帮助。

Source -> Dependencies
A -> B , C
B -> D , E , F
C -> G , H 
D->I
E-> J , K , L
F -> null
G -> null
H -> null
I -> null
J -> null
K -> null
L -> null

使用 BFS 遍历图形。将节点添加到新图形。从任何开始。 （虽然这个解决方案不是递归的，但它有效）

例如，您的情况：

从节点 A 开始图形。

  1. G(A)

  2. G(A->B) //现在寻找B的依赖关系

  3. G(A->B->D) //现在是D，依此类推

  4. G(A->B->D->I)

  5. G(A->B->D->I, B->E)

  6. G(A->B->D->I, B->E->J)

  7. G(A->B->D->I, B->E->J, E->K, E->L)

  8. G(A->B->D->I, B->E->J, E->K, E->L, B->F)

  9. G(A->B->D->I, B->E->J, E->K, E->L, B->F, A->C )

  10. G(A->B->D->I, B->E->J, E->K, E->L, B->F, A->C ->G->H) ---现在这将是您的最终图表。

现在您的最终图表，在本例中是单个图表。它可能是一组断开连接的组件。对于现在的每个组件，您都可以执行 DFS，这将为您提供答案。

eg. 在此图中，对于（根）节点A，所有叶子都将是其依赖项。对于 B，我们有 (F,I,J,K and L) 等等