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

Question

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

得到的结构可以表示为有向无环图(DAG),其中项目是图表拓扑底部的汇点,顶部类别是源.请注意,虽然某些类别可能已经定义得很好,但很多都是用户定义的,并且可能非常混乱.

例:

_{(来源:theuprightape.net)}

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

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

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

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

维基百科上列出的图遍历算法似乎都关注于找到特定节点或两个节点之间最短或最有效的路由.我认为两者都不是我想要的,或者我只是没有看到这对我的问题有何影响？我还应该在哪里阅读？

Answer 1

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