Probleme mit einem einfachen Abhängigkeitsalgorithmus

Question

In meiner Webapp haben wir viele Felder, die andere Felder zusammenfassen, und diese Felder fassen mehr Felder zusammen. Ich weiß, dass dies ein gerichteter azyklischer Graph ist.

Wenn die Seite geladen wird, berechne ich Werte für alle Felder. Was ich wirklich versuche, ist, meine DAG in eine eindimensionale Liste umzuwandeln, die einen effizienten Befehl zum Berechnen der Felder enthalten würde.

Zum Beispiel: A = B + D, D = B + C , B = C + E Effiziente Berechnungsreihenfolge: E -> C -> B -> D -> A

Im Moment führt mein Algorithmus iterativ nur einfache Einfügungen in eine Liste durch, aber ich bin in einige Situationen geraten Das fängt an zu brechen. Ich denke, was wäre stattdessen erforderlich wäre, alle Abhängigkeiten in einer Baumstruktur zu erarbeiten, und von dort in die eindimensionale Form umzuwandeln? Gibt es einen einfachen Algorithmus, um einen solchen Baum in eine effiziente Ordnung umzuwandeln?

Answer 1

Suchen Sie nach topological sort? Dies erlegt einer DAG eine Reihenfolge (eine Sequenz oder Liste) auf. Es wird beispielsweise von Tabellenkalkulationen verwendet, um Abhängigkeiten zwischen Zellen für Berechnungen herauszufinden.

Answer 2

Was Sie wollen, ist eine Tiefensuche.

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

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

    AddToList(F) 
} 

Dann rufen Sie einfach ExamineField() auf jedes Feld wiederum, und die Liste wird in einer optimalen Reihenfolge entsprechend Ihrer Spezifikation bestückt werden.

Beachten Sie, dass, wenn die Felder zyklisch sind (dh Sie haben etwas wie A = B + C, B = A + D) muss der Algorithmus so geändert werden, dass er nicht in eine Endlosschleife geht .

Für Ihr Beispiel würde gehen die Anrufe:

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) 

Und die Liste wäre sehr viel am Ende C, E, B, D, A.