如何通过DAG中的一组给定节点找到所有路径？ [英] How do I find all paths through a set of given nodes in a DAG?

问题描述

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

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.

结果结构可以表示为定向非循环图（DAG），其中项目汇集在图形拓扑底部，顶层类别是源。请注意，虽然某些类别可能被很好地定义，但很多内容将被用户定义，可能会非常混乱。

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.

示例：

示例数据http://theuprightape.net/dag.png

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

On that structure, I want to perform the following operations:

• 查找所有项目（sink）在一个特定节点下方（欧洲的所有项目）


• 找到所有通过一组n个节点（通过SMTP发送的所有项目）的路径（如果有的话）。 com）


• 查找位于所有节点下方的所有节点（交点：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?

中列出的noreferrer>图遍历算法都似乎关注于找到一个特定的节点，或者两个节点之间最短或最有效的路由。我认为两者都不是我想要的，或者我没有看到这是如何适用于我的问题？我应该读什么？

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?

推荐答案

在我看来，它对所有3个问题基本上是相同的操作。你一直在问查找节点Y以下的所有X，其中X是类型Z。所有你需要的是定位节点下面的所有节点的通用机制，（解决Q3），然后您可以过滤'nodetype = sink'的结果（解决Q1）。对于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.

这篇关于如何通过DAG中的一组给定节点找到所有路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！