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

Question

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

结果结构可以表示为 Directed Acyclic Graph (DAG)其中项目是图表拓扑底部的接收器，顶部类别是源。请注意，虽然某些类别可能定义明确，但很多类别将由用户定义并且可能非常困惑。

例子:

_{(来源:theuprightape.net)}

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

• 查找特定节点下的所有项目(汇)(欧洲的所有项目)
• 找到通过一组 n 个节点的所有路径(如果有的话)(所有通过 SMTP 从 example.com 发送的项目)
• 找到位于所有节点集下方的所有节点(交叉点:goyish brown foods)

第一个看起来很简单:从节点开始，沿着所有可能的路径到达底部并在那里收集项目。但是，有更快的方法吗？记住我已经通过的节点可能有助于避免不必要的重复，但还有更多优化吗？

我该如何处理第二个？第一步似乎是确定集合中每个节点的高度，以确定从哪个节点开始，然后找到低于该节点的所有路径，其中包括集合的其余部分。但这是最好的(甚至是好的)方法吗？

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

Answer 1

在我看来，所有 3 个问题的操作本质上是相同的。您总是在问“查找节点 Y 下的所有 X，其中 X 的类型为 Z”。您所需要的只是一个通用机制，用于“定位节点下的所有节点”(解决 Q3)，然后您可以过滤“nodetype=sink”的结果(解决 Q1)。对于 Q2，您有起点(您的节点集)和终点(起点以下的任何汇)，因此您的解决方案集是从指定的起始节点到汇的所有路径。所以我建议您基本上拥有的是一棵树，而基本的树遍历算法将是可行的方法。