java - 如何检测无用的依赖关系？

Question

假设我在某些任务之间有一堆依赖关系:

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

这样A --> B 意味着B 只能在A 完成后才能运行。

我怎样才能检测并删除无用的依赖项？

在本例中，它是“A --> D”，因为 D 依赖于 C，而 C 又依赖于 B，而 B 又依赖于 A。

Answer 1

将其转换为邻接矩阵，您将得到以下结果:

  A B C D E F G
A 0 1 0 1 0 0 0
B 0 0 1 0 0 0 0
C 0 0 0 1 0 0 0
D 0 0 0 0 0 0 0
E 0 0 0 0 0 1 0
F 0 0 0 0 0 0 1
G 0 0 0 0 0 0 0

将此矩阵与其自身相乘将产生一个新矩阵，告诉您从每个节点到每个节点有多少种不同的方式，使用两个步骤。再次相乘，您将看到三步的结果，依此类推。

一般来说，A 乘以 k 将产生一个矩阵，告诉您从一个节点到另一个节点的不同路径的数量，需要 k 步。

使用此信息，您可以尝试发现多个路径描述的节点/任务之间的依赖关系。在 A 和 D 之间，您将看到一条包含 A^1 (A --> D) 和 A^3 (A --> B --> C --> D) 的路径。

一旦发现从节点 X 到节点 Y 的多条路径，您就可以删除原始邻接矩阵中的直接依赖关系。