12

我有一个由我的应用程序用户分类的项目列表（下面的蓝色节点）。类别本身可以被分组和分类。

生成的结构可以表示为有向无环图 (DAG)，其中项目是图拓扑底部的汇，顶部类别是源。请注意，虽然某些类别可能定义明确，但很多类别将由用户定义并且可能非常混乱。

例子：

示例数据
（来源：theuprightape.net）

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

  • 查找特定节点下的所有项目（汇）（欧洲的所有项目）
  • 查找通过所有一组 n 个节点的所有路径（如果有）（所有通过 SMTP 从 example.com 发送的项目）
  • 找到位于所有节点集下方的所有节点（交叉点：goyish brown foods）

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

我该如何处理第二个？第一步似乎是确定集合中每个节点的高度，以确定从哪个（s）开始，然后找到低于该集合其余部分的所有路径。但这是最好的（甚至是好的）方法吗？

维基百科上列出的图遍历算法似乎都与寻找特定节点或两个节点之间最短或最有效的路线有关。我认为两者都不是我想要的，还是我只是看不到这如何适用于我的问题？我还应该在哪里阅读？

4

2 回答 2

2

尽管您的图是非循环的，但您引用的操作让我想起了控制流图分析的类似方面。有一套丰富的基于优势的算法可能适用。例如，您的第三次操作让我想起了计算优势前沿；我相信如果您暂时引入“入口”和“出口”节点，该算法将直接起作用。入口节点连接“给定的节点集”，出口节点连接汇点。

另请参阅Robert Tarjan 的基本算法。

于 2008-11-26T20:54:26.260 回答
2

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

于 2008-12-02T18:29:59.000 回答