単純な依存アルゴリズムの問​​題

Question

私のWebアプリケーションでは、他のフィールドを合計するフィールドが多数あり、それらのフィールドの合計フィールドが増えています。私はこれが有向非循環グラフであることを知っています。

ページが読み込まれると、すべてのフィールドの値が計算されます。私が実際にやろうとしているのは、DAGをフィールドを計算するための効率的な命令を含む1次元リストに変換することです。

例： A = B + D、D = B + C今すぐ私のアルゴリズムはリストへの単純な挿入を繰り返しますが、私はいくつかの状況に遭遇しました。それは壊れ始める。私は代わりに、ツリー構造にすべての依存関係を取り除くことが必要であろうと思っています。そこから、それを一次元の形に変換しますか？そのようなツリーを効率的な順序に変換する簡単なアルゴリズムはありますか？

Answer 1

topological sortをお探しですか？これにより、DAGに順序（リストまたはリスト）が適用されます。これは、スプレッドシートなどで、計算のためのセル間の依存関係を把握するために使用されます。

Answer 2

奥行きの検索が欲しいものです。

function ExamineField(Field F) 
{ 
    if (F.already_in_list) 
     return 

    foreach C child of F 
    { 
     call ExamineField(C) 
    } 

    AddToList(F) 
} 

は、それからちょうど順番に各フィールドにExamineField（）を呼び出し、およびリストは、あなたの仕様に応じて最適な順序で読み込まれます。

フィールドがサイクリック（つまり、A = B + C、B = A + Dなど）である場合、アルゴリズムは無限ループにならないように変更する必要があります。

ご例えば、呼び出しが行くだろう：

ExamineField(A) 
    ExamineField(B) 
    ExamineField(C) 
     AddToList(C) 
    ExamineField(E) 
     AddToList(E) 
    AddToList(B) 
    ExamineField(D) 
    ExamineField(B) 
     (already in list, nothing happens) 
    ExamineField(C) 
     (already in list, nothing happens) 
    AddToList(D) 
    AddToList(A) 
ExamineField(B) 
    (already in list, nothing happens) 
ExamineField(C) 
    (already in list, nothing happens) 
ExamineField(D) 
    (already in list, nothing happens) 
ExamineField(E) 
    (already in list, nothing happens) 

を、リストがC、E、B、D、A.