我想知道是否有一個有效的算法S = F（v，G）從DAG G =（V，E）中構造一個子圖S，使得S中的所有路徑都包含頂點v的V.如果是這樣，有可能有效地將F擴展到F'（N，G）以用於一組頂點N.我開放給任何用於最初存儲DAG G的數據結構。子圖算法
實際上，我忘記添加的一個條件是G有一個獨特的頂點r，沒有傳入邊，路徑必須是其中d是沒有傳出邊的頂點的形式。
我錯過的另一個條件是給定擴展F'（N，G），使得對於所有v，w的N，如果其中w是匯，那麼我們應該忽視路徑< r，..，v，..，x>其中x！= w。
其實我有一個解決方案，但它不適合，當·V> 2000和＃N> 2
我假設你正在尋找G =（{R} + V的最大子小號+ {d}，E）其中，r是唯一的源節點和d是水槽，使得從r到d的每個路徑通過的特定結點v
我提出的算法：
找到所有的r和v之間的路徑使用例如在Find the paths between two given nodes?提供的答案
查找v之間的所有路徑並使用相同的算法。因爲G是無環的，沒有從v到d的路徑會導致回到步驟1中。因此已經發現，一個路徑在所得圖表r和d之間的所有路徑將通過訴
如果存在從G中的每個頂點到v的路徑（記住G是DAG），則S可以是G本身。實際上，我忘記添加的一個條件是，G具有唯一的頂點r，沒有入邊，路徑必須爲
即使有上述情況，仍然存在一個簡單的解決方案。任何
謝謝。它應該是滿足條件的最大子圖。不幸的是，當我們考慮多於一個這樣的v時，你的解決方案不能很好地擴展（它確實與我原來的解決方案非常相似）。另一個我錯過的條件是給定了擴展的F'（N，G）如果
合力圖包含節點可從v到達並且節點v可從（或在轉置的子圖中可從v到達的節點）到達。獲取可達節點集可以高效完成。
對於一組節點，這可能很容易擴展：您應該在廣度優先搜索開始時將它們全部添加。
難道這是作業嗎？ – Sebastian 2009-12-03 13:22:53
如果這是家庭作業，請標記爲這樣。 – 2009-12-03 13:23:19
這不是作業。 – Peter 2009-12-03 13:45:15