如何找到通过 DAG 中一组给定节点的所有路径？
我有一个项目列表（下面的蓝色节点），这些项目按我的应用程序的用户进行分类。 类别本身可以自行分组和分类。
生成的结构可以表示为 有向无环图 (DAG)，其中项目的汇点为图表拓扑的底部和顶部类别是源。 请注意，虽然某些类别可能定义良好，但很多类别将由用户定义，并且可能非常混乱。
示例：
(来源：theuprightape.net)
在该结构上，我想执行以下操作：
- 查找特定节点下的所有项目（接收器）（欧洲的所有项目）
- 查找经过一组 n 个节点的所有路径（如果有）（从 example.com 通过 SMTP 发送的所有项目）
- 查找所有位于所有一组节点下方的节点（交叉点：褐色食物）
第一个似乎非常简单：从节点开始，沿着所有可能的路径到达底部并收集那里的项目。 然而，有没有更快的方法呢？ 记住我已经经过的节点可能有助于避免不必要的重复，但是还有更多的优化吗？
我该如何处理第二个？ 似乎第一步是确定集合中每个节点的高度，以确定从哪个节点开始，然后找到包含集合其余部分的所有路径。 但这是最好的（甚至是好的）方法吗？
维基百科上列出的图遍历算法似乎都与查找特定节点或两个节点之间的最短或最有效的路线。 我认为两者都不是我想要的，或者我只是没有看到这如何适用于我的问题？ 我还应该在哪里阅读？
I have a list of items (blue nodes below) which are categorized by the users of my application. The categories themselves can be grouped and categorized themselves.
The resulting structure can be represented as a Directed Acyclic Graph (DAG) where the items are sinks at the bottom of the graph's topology and the top categories are sources. Note that while some of the categories might be well defined, a lot is going to be user defined and might be very messy.
Example:
(source: theuprightape.net)
On that structure, I want to perform the following operations:
- find all items (sinks) below a particular node (all items in Europe)
- find all paths (if any) that pass through all of a set of n nodes (all items sent via SMTP from example.com)
- find all nodes that lie below all of a set of nodes (intersection: goyish brown foods)
The first seems quite straightforward: start at the node, follow all possible paths to the bottom and collect the items there. However, is there a faster approach? Remembering the nodes I already passed through probably helps avoiding unnecessary repetition, but are there more optimizations?
How do I go about the second one? It seems that the first step would be to determine the height of each node in the set, as to determine at which one(s) to start and then find all paths below that which include the rest of the set. But is this the best (or even a good) approach?
The graph traversal algorithms listed at Wikipedia all seem to be concerned with either finding a particular node or the shortest or otherwise most effective route between two nodes. I think both is not what I want, or did I just fail to see how this applies to my problem? Where else should I read?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在我看来，这三个问题的操作本质上是相同的。 你总是问“找到节点 Y 下面的所有 X，其中 X 是 Z 类型”。 您所需要的只是“定位节点下方的所有节点”的通用机制（解决问题 3），然后您可以过滤“nodetype=sink”的结果（解决问题 1）。 对于 Q2，您有起点（您的节点集）和终点（起点以下的任何接收器），因此您的解决方案集是从指定的起始节点到接收器的所有路径。 所以我建议你基本上拥有的是一棵树，并且基本的树遍历算法将是可行的方法。
It seems to me that its essentially the same operation for all 3 questions. You're always asking "Find all X below node(s) Y, where X is of type Z". All you need is a generic mechanism for 'locate all nodes below node', (solves Q3) and then you can filter the results for 'nodetype=sink' (solves Q1). For Q2, you have the starting-point (your node set) and your ending point (any sink below the starting point) so your solution set is all paths from starting node specified to the sink. So I would suggest that what you basically have a is a tree, and basic tree-traversal algorithms would be the way to go.
尽管您的图是非循环的，但您引用的操作让我想起了控制流图分析的类似方面。 有一组丰富的基于支配性的算法可能适用。 例如，你的第三个操作让我想起了计算优势前沿； 我相信如果你暂时引入“入口”和“出口”节点，算法将直接起作用。 入口节点连接“给定的节点集”，出口节点连接接收器。
另请参阅 Robert Tarjan 的基本算法。
Despite the fact that your graph is acyclic, the operations you cite remind me of similar aspects of control flow graph analysis. There is a rich set of algorithms based on dominance that may be applicable. For example, your third operation reminds me od computing dominance frontiers; I believe that algorithm would work directly if you temporarily introduce "entry" and "exit" nodes. The entry node connects the "given set of nodes" and the exit nodes connects the sinks.
Also see Robert Tarjan's basic algorithms.