如何找到通过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.

所产生的结构可以重新$ P $所在的项目是汇在图形的拓扑的底部和顶部类别的来源。请注意，尽管有些类别可能会被明确定义，很多将是用户定义的，而且可能会很凌乱。

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.

例如：

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

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

• 找到的所有项目（汇）的特定节点下（在欧洲的所有项目）
• 找到所有路径（如果有的话）通过所有的一组n个节点的（所有物品通过SMTP从example.com发送）
• 找到了躺在下面所有的一组节点的所有节点（交叉点：goyish棕色食品）

第一个似乎很简单：开始的节点，请按照所有可能的路径的底部和收集的物品有。然而，有一个更快的方法吗？记住我已经通过可能有助于避免不必要的重复的节点，但有更多的优化？

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?

推荐答案

在我看来，其本质上是相同的操作对所有3个问题。你总是问：请看下面的网络节点Y，其中X是Z型的所有的X。所有你需要的是一个通用的机制，它可以找到以下节点的所有节点，（解决Q3），然后你可以过滤结果为'NODETYPE =汇（解决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屋！