如何在DAG中找到通过一组给定节点的所有路径？

Question

我有一个项目列表（下面的蓝色节点），由我的应用程序的用户分类。类别本身可以自行分组和分类。

得到的结构可以表示为Directed Acyclic Graph (DAG)，其中项目在图形拓扑的底部汇集，顶部类别是源。请注意，虽然某些类别可能已经定义得很好，但很多都是用户定义的，并且可能非常混乱。

例：

（来源：theuprightape.net）

在该结构上，我想执行以下操作：

• 查找特定节点下方的所有项目（接收器）（欧洲所有项目）
• 查找通过所有n个节点集的所有路径（如果有）（通过SMTP从example.com发送的所有项目）
• 找到位于所有节点下方的所有节点（交叉点：goyish brown foods）

第一个似乎非常简单：从节点开始，按照所有可能的路径到底部并收集那里的项目。但是，有更快的方法吗？记住我已经通过的节点可能有助于避免不必要的重复，但还有更多的优化吗？

我怎么去第二个呢？似乎第一步是确定集合中每个节点的高度，以确定在哪个（s）开始，然后找到包括集合其余部分的所有路径。但这是最好的（甚至是好的）方法吗？

graph traversal algorithms listed at Wikipedia似乎都关注于找到特定节点或两个节点之间的最短或最有效的路由。我认为两者都不是我想要的，或者我只是没有看到这对我的问题有何影响？我还应该在哪里阅读？

Answer 1

在我看来，它对所有3个问题的操作基本相同。你总是问“在节点Y下找到所有X，其中X是Z型”。您只需要“定位节点下的所有节点”的通用机制，（解决Q3）然后您可以过滤“nodetype = sink”的结果（解决Q1）。对于Q2，您有起点（您的节点集）和结束点（起点下面的任何接收器），因此您的解决方案集是从指定的起始节点到接收器的所有路径。所以我建议你基本上拥有的是一棵树，基本的树遍历算法将是最佳选择。

Answer 2

尽管您的图表是非循环的，但您引用的操作让我想起了控制流图分析的类似方面。基于dominance的丰富算法可能适用。例如，你的第三个操作提醒我计算优势边界;我相信如果你暂时引入“入口”和“退出”节点，算法将直接工作。入口节点连接“给定节点集”，出口节点连接接收器。

另请参阅Robert Tarjan's基本算法。