簡單依賴算法的問題

在我的webapp中，我們有許多領域總結其他領域，這些領域總結更多的領域。我知道這是一個有向無環圖。簡單依賴算法的問題

當頁面加載時，我計算所有字段的值。我真正想要做的就是將我的DAG轉換爲一維列表，其中包含一個計算字段的有效順序。

例如： A = B + D，D = B + C ，B = C + E 有效的計算順序：E - > C - > B - > D - > A

現在我的算法只是簡單地迭代插入List，但我遇到了一些情況開始中斷。我在想什麼需要改爲將所有依賴項編譯爲樹結構，然後將其轉換爲一維形式？有沒有一種簡單的算法將這種樹轉化爲有效的排序？

來源

2009-07-28 Coxy

你是在找topological sort？這在DAG上施加了一個排序（一個序列或列表）。例如，它被電子表格用來計算單元之間的依賴關係以進行計算。

來源

2009-07-28 06:24:20 quark

非常感謝，這正是術語，我之後。 – Coxy 2009-07-28 08:03:30

你想要的是深度優先搜索。

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

來源

2009-07-28 06:31:47 caf

非常感謝這個例子！這正是我想要做的，儘管我最終選擇了迭代算法。 – Coxy 2009-07-28 08:04:06

簡單依賴算法的問題

回答

相關問題