开发者

Graph iteration from bottom to top algorithm?

Given this dependency graph: What's a "good" approach to iterate through it from bottom to top?

My expected results for each "cycle" are:

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

Brainstorming

// 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 ?
}

Reason wh开发者_Python百科y "Depth-first search" does not work:

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

Algorithm

I really don't want to reinvent the wheel: So is there already an algorithm which solve this problem or does anyone have a "clever" approach?


You probably want topological sort to go through the graph of dependencies. You can do this with DFS (depth-first search) and BFS (breath-first search) as well -- both mentioned in pseudocode on the wikipedia link. Both are linear in input size.


Do a topological sort which gives nodes in order of depth. Then if you want to find the boundaries between different depths, use a dynamic programming algorithm. This solution is linear in the size of the graph, O(|V| + |E|).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜