1

鉴于此依赖关系图：从下到上遍历它的“好”方法是什么？

我对每个“周期”的预期结果是：

Iteration step "1": Project B, Project D, Project Z, Project O 
Iteration step "2": Project C, Project W, Project V, Project Q
Iteration step "3": Project A, Project M
Iteration step "4": Start X // End

头脑风暴

// PSEUDO CODE: Find and return "next projects fixes" to perform. 
// -> All projects with no or already fixed dependencies. 
FUNC FindNextDependciesToFix ( NODE StartNode, BYREF LIST<NODE> RefNextProjectsToFix )
{    
 ... // Algorithm ?
}

“深度优先搜索”不起作用的原因：

DO
{
 FindNextDependciesToFix (StartX, FixNextList);
 CallASYNCAndWaitForEndOfFix (FixNextList);
 // <- Wait till end of project fix (async...) 
} WHILE ( FixNextList.IsEmpty() );

算法

我真的不想重新发明轮子：那么是否已经有一种算法可以解决这个问题，或者有没有人有一个“聪明”的方法？

4

2 回答 2

1

您可能希望拓扑排序通过依赖关系图。您也可以使用 DFS（深度优先搜索）和 BFS（呼吸优先搜索）来执行此操作 - 维基百科链接上的伪代码中都提到了这两种方法。两者的输入大小都是线性的。

于 2011-03-04T21:54:40.250 回答
0

进行拓扑排序，按深度顺序给出节点。然后，如果您想找到不同深度之间的边界，请使用动态规划算法。这个解在图的大小上是线性的，O(|V| + |E|)。

于 2011-03-04T21:55:00.233 回答