我有一個由用戶創建的有向無環圖，其中圖的每個節點（頂點）代表對某些資料執行的操作。節點的輸出取決于其輸入（顯然），并且該輸入由其父節點提供。然后將輸出傳遞給它的孩子。回圈保證不存在，因此可以忽略。
該圖的作業原理與
盡管依賴于，但傳統的廣度優先遍歷將導致在D之前被評估。BDB
我試過反向進行廣度優先遍歷（即從O1和O2節點開始，向上遍歷圖），但我似乎遇到了同樣的問題。反向廣度優先遍歷將訪問Dbefore B，因此I2before A，導致I2排序after A，盡管A取決于I2。
我確定我在這里遺漏了一些相對簡單的東西，而且我覺得反向遍歷是關鍵，但我似乎無法將頭圍繞它并使所有部分都適合。我想一個潛在的解決方案是按預期使用反向遍歷，但不是避免多次訪問每個節點，而是每次出現時訪問每個節點，確保它具有絕對正確的順序。但是多次訪問每個節點以及隨之而來的指數擴展是一個非常沒有吸引力的解決方案。
對于此類問題，是否有眾所周知的有效演算法？
uj5u.com熱心網友回復：
是的，有一個眾所周知的高效演算法。這是拓撲排序。
創建一個包含所有節點及其相應入度的字典，我們稱之為indegree_dic. in-degree 是該節點的父/或傳入邊的數量。有一組S入度為零的節點。
取自維基百科頁面，稍作修改：
L ← Empty list that will contain the nodes sorted topologically
S ← Set of all nodes with no incoming edge that haven't been added to L yet
while S is not empty do
remove a node n from S
add n to L
for each child node m of n do
decrement m's indegree
if indegree_dic[m] equals zero then
delete m from indegree_dic
insert m into S
if indegree_dic has length > 0 then
return error (graph is not a DAG)
else
return L (a topologically sorted order)
這種型別并不是唯一的。我提到這一點是因為它對你的演算法有一些影響。
現在，每當任何節點發生更改時，您都可以安全地避免重新計算拓撲排序串列中位于更改節點之前的任何節點，但需要重新計算在其之后的節點。如果您在計算中遵循排序串列，則可以確保所有父項都在其子項之前處理。
該演算法不是最優的，因為在更改的節點之后可能存在不是該節點的子節點的節點。就像在以下場景中一樣：
A
/ \
B C
一種正確的拓撲排序是[A, B, C]。現在，假設B發生了變化。您跳過，A因為它沒有任何變化，但重新計算，C因為它在 之后B。但你實際上不需要，因為B對C任何東西都沒有影響。
如果這個影響不大，你可以使用這個演算法，讓實作更容易，更不容易出錯。但如果效率是關鍵，這里有一些想法可能會有所幫助：
您可以每次都進行拓撲排序，并將哪個節點發生變化作為一個因素。從
S上述演算法中選擇節點時，在選擇更改的節點之前，請盡可能選擇其他所有節點。換句話說，您S僅在S長度為 1時從中選擇更改的節點。這保證您處理不在其之前的更改節點的層次結構之下的每個節點。當排序比處理節點便宜得多時，這種方法會有所幫助。另一種我不確定是否正確的方法是在拓撲排序串列中查看已更改的節點，并僅在您到達已更改節點的第一個子節點時才開始處理。
另一種方法依賴于想法 1，但如果您可以進行一些預處理，則很有幫助。您可以為每個節點被更改的情況創建拓撲排序。當節點發生更改時，您會嘗試盡可能晚地將其放入排序中。您將節點中的所有這些排序保存到排序字典中，并根據哪個節點發生更改來選擇該排序。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/380278.html