我该如何找到所有道路通过一组给出的节点在达格?

Question

我有一个的项目清单(蓝色的节点下文)，它们分类的用户的我应用程序。该类别本身可以进行分组和分类本身。

得到的结构可以表示为 针对环图(DAG) 项目的水槽底部的曲线图的拓扑结构和顶类别的来源。请注意，虽然某些类别可能会被很好的定义，很多是要用户定义以及可能非常混乱。

例如：

_{(资料来源： theuprightape.net)}

在这一结构，我希望执行下列行动：

• 找到的所有项目(水槽)下面的一个特别节点(所有项目在欧洲)
• 找到所有的路径(如果有任何)，通过所有的一组n节(所有项目的发送的通过SMTP从example.com)
• 找到的所有节点的那躺下所有的一套节点(交叉点:goyish棕色的食物)

第一，似乎相当直截了当的：开始点，按照所有可能的路径底和收集项目。然而，有没有更快的方法？记住这点我已经通过了可能有助于避免不必要的重复，但是还有更多的优化?

我如何去关于第二个?看来，第一步将是确定高度的各个节点的设置，以确定在哪一个(s)开始，然后发现所有的路径如下，其中包括其余部分设置。但是这个的最佳(甚或良好)的做法？

的 图遍历列出的算法在维基百科 都似乎感到关切的是与寻找一个特别的节点，或最短或否则最有效的途径之间的两个节点。我想两者都不是我想要什么，或者我只是看不出这适用于我的问题吗？在别的地方我应该读什么书？

Answer 1

在我看来，其本质上相同的操作所有3个问题。你总是问"找到的所有X下节点(s)Y，X的类型Z"。所有你需要的是一个通用的机制'找到的所有节点下的节点',(解决了3)然后你可以过滤器的结果'类型=沉'(解决Q1)。第2季度，你必须起始点(节点设置)以及你的结束点(任何水槽下面开始点)使你的解决方案的设置是所有的路径从开始节点指定的水槽。因此，我谨建议，什么基本上你有一棵树，并基本树历的算法将要走的道路。

Answer 2

尽管事实上，你的曲线图是非循环，操你举提醒我的类似方面的控制流程图表分析。有一套丰富的算法基础上的 主导地位 这可能是适用的。例如，第三操作让我想起了od计算的主导地位的边境;我认为算法的工作如果直接你暂时介绍"入口"和"出口"的节点。该入境点连接的"给定点"和出口节点连接器。

也见 罗伯特*陶尔扬的 基本的算法。