java - 考虑多重约束，如何处理任务之间的依赖关系？

Question

我正在开发一个 Java 程序，该程序接受一个输入文件，其中包含一堆任务之间的依赖关系，如下所示:

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

“C --> D”表示任务 D 只能在 C 完成后开始，但并不一定意味着 D 紧随 C 之后。如果任务彼此独立，它们也可以并行运行(A &例如E)。

程序应该处理所有这些依赖项并考虑以下约束生成输出依赖项列表:

• 查找所有源(在本例中为 A 和 E)并从源开始对依赖项进行排序:

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

• 删除所有无用的依赖项(在本例中:A --> D)

• 最后，通过在“Start”和源之间添加依赖关系，添加“Start”任务作为所有依赖关系的根。生成的输出列表应如下所示:

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

然后我必须使用“Jung”等专用库从上面的依赖项列表中显示有根 TreeMap 。

关于如何处理所有这些约束有什么想法吗？

预先感谢您的帮助。

Answer 1

查找来源很简单；只需询问每个顶点是否有任何传入边即可。

对于其余的，基本上你想从图中提取生成树；有几种算法可以做到这一点。