訂單清單通過依賴

考慮以下列表：訂單清單通過依賴

var modules = new List<Module>() { 
    new Module() { Name = "Audits", Dependencies = new[] { "Logs" } }, 
    new Module() { Name = "Blog", Dependencies = new[] { "Content", "Tags" } }, 
    new Module() { Name = "Content", Dependencies = new[] { "Audits" } }, 
    new Module() { Name = "Logs" }, 
    new Module() { Name = "Tags" } 
};

我需要創建一種方式，這樣是最可靠的組件位於頂部以編程方式訂購此列表。因此，使用上面的例子中所需的順序將是：

日誌
審計
內容
標籤
博客

由於「內容」具有的「審覈的依賴「然後」審計「首先出現。但由於「審計」依賴於「日誌」，因此「日誌」位於「審計」之上。「博客」最後出現，因爲它依賴於「內容」和「標籤」，因此他們上面。

我希望我已經足夠清楚地描述了我的問題。我敢肯定，有一些聰明的算法來處理這個問題，並儘可能地提高效率，但到目前爲止它已經提到了我。如果有人能指出我正確的方向，我會很感激。

感謝

來源

2014-02-06 nfplee

您所描述的問題稱爲topological sort：給定部分排序，嘗試查找尊重該排序的線性描述。

典型算法來解決這個問題需要O(|V| + |E|)時間，其中|V|是頂點的數目（模塊在你的例子）和|E|是邊緣（在您的示例依賴關係）的數量。

鏈接的維基百科條款還提供pseudo code。這需要一些記錄來將算法轉換爲示例，但它相對比較簡單。

來源

2014-02-06 18:46:18

我對代碼使用了下面的回答http://stackoverflow.com/a/11027096/155899，但感謝給我算法的名稱，以便我可以搜索正確的解決方案。 – nfplee

最簡單的方法是創建值之間的比較功能排序基於依賴

static int CompareModules(Module left, Module right) { 
    if (left.Dependencies.Contains(right.Name)) { 
    return 1; 
    } 

    if (right.Dependencies.Contains(left.Name)) { 
    return -1; 
    } 

    return left.Dependencies.Length - right.Dependencies.Length; 
}

然後以此爲參數List<T>.Sort

modules.Sort(CompareModules);

注意，這樣本假定Dependencies是空數組，當它們沒有依賴關係時，並且沒有循環變量筆劃

來源

2014-02-06 16:57:34 JaredPar

這不考慮傳遞性依賴性，根據排序實現，這將導致錯誤的結果，甚至是無限循環。 –

訂單清單通過依賴

回答

相關問題