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 に答える