拓撲分類變種算法

Question

我有一組數據需要執行拓撲排序，有一些假設和約束條件，我想知道是否有人知道現有的適用於此的高效算法。

• 數據關係已知形成一個DAG（所以沒有擔心的週期）。
• 從A到B的邊表示A依賴於B，所以B必須在拓撲排序中出現在A之前。
• 該圖不一定是連接的;也就是說，對於任何兩個節點N和M，可能無法通過跟隨邊緣從N到M（即使忽略邊緣方向）。
• 數據關係是單獨關聯的。這意味着當存在從A指向B的邊時，只有A節包含有關邊的存在的信息。

該問題可以如下配製：

鑑於圖形G一組節點S的哪個可以或可以不具有入邊，發現以下組成的子圖G'的拓撲排序G中的所有節點都可從集合S（服從邊緣方向）中的任何節點到達。

這混淆的常用方法拓撲排序，因爲他們需要在集中的節點S沒有任何入邊，這是一件好事，是不是真的在我的情況。出現問題的情況是：

A --> B --> D 
| ^ ^
|  |  | 
\---> C ----/ 

哪裏S = {B, C}。一個合適的排序是D, B, C，但如果一個正常的拓撲排序算法碰巧在C之前考慮B，它將以C, D, B結束，這是完全錯誤的。 （請注意，A不會出現在最終的排序，因爲它不是來自S可達，它的出現給所有在S節點可能有入邊的例子）

現在，我必須想象這是這是一個長期解決的問題，因爲在一個安裝命令中指定多個軟件包時，這基本上就是像apt和yum這樣的程序必須執行的操作。但是，當我搜索「依賴關係解析算法」這樣的關鍵字句時，我得到的結果描述了正常的拓撲排序，這不能處理這種特殊情況。

我可以想到一些方法來做到這一點，但沒有一個看起來特別優雅。我想知道是否有人有一些指向適當算法的指針，最好是能夠在數據上一次操作的指針。

Answer 1

我不認爲你會發現一個算法，可以做到這一點的數據一次通過。我將執行廣度優先搜索，從S中的節點開始，然後對生成的子圖進行拓撲排序。

Answer 2

我認爲你可以對整個圖進行拓撲排序，然後只選擇節點集中可到達的節點（可以從集合中的節點進行一些深度優先搜索，排序，如果以前沒有訪問過，則會進入節點的子樹）。