如何通過DAG中的一組給定節點找到所有路徑？

Question

我有一個由我的應用程序的用戶分類的項目列表（下面的藍色節點）。類別本身可以自己分組和分類。

生成的結構可以表示爲Directed Acyclic Graph (DAG)，其中項目在圖形拓撲的底部爲匯，頂部類別爲源。請注意，雖然某些類別可能已被很好地定義，但很多將會是用戶定義的，可能會非常混亂。

例子：

example data http://theuprightape.net/dag.png

在這個結構，我想執行以下操作：

• 找到一個特定節點下的所有項目（匯）（所有項目在歐洲）
• 查找所有通過一組n個節點（通過SMTP從example.com發送的所有項目）的路徑（如果有的話）
• f ind位於所有節點下方的所有節點（交叉點：goyish brown食品）

第一個看起來很直接：從節點開始，沿着所有可能的路徑到達底部並收集項目。但是，有沒有更快的方法？記住我已經通過的節點可能有助於避免不必要的重複，但還有更多優化嗎？

我該如何解決第二個問題？看起來，第一步是確定集合中每個節點的高度，以確定在哪個節點開始，然後找到包含集合其餘部分的所有路徑。但這是最好的（甚至是好的）方法嗎？

graph traversal algorithms listed at Wikipedia似乎都在尋找一個特定的節點或兩個節點之間最短或最有效的路由。我認爲這兩者不是我想要的，還是我不明白這是如何適用於我的問題？我應該在哪裏閱讀？

Answer 1

在我看來，它對於所有3個問題的操作基本相同。你總是問「在節點Y下找到所有X，其中X是Z型」。所有你需要的是'找到節點下的所有節點'的通用機制（解決Q3），然後你可以過濾'nodetype = sink'的結果（解決Q1）。對於第二季度，您有起點（您的節點集）和您的終點（任何匯點低於起點），因此您的解決方案集是從指定的起始節點到匯的所有路徑。所以我會建議你基本上有一棵樹，基本的樹遍歷算法將是一條路。

Answer 2

儘管您的圖形是非循環的，但您引用的操作讓我想起控制流圖分析的類似方面。有一套基於dominance的豐富算法可能適用。例如，您的第三個操作讓我想起了計算優勢領域;我相信如果你臨時引入「入口」和「出口」節點，算法會直接起作用。入口節點連接「給定節點集」，出口節點連接匯。基本算法見Robert Tarjan's。