我有一个项目列表(如下图中的蓝色节点),由我的应用程序用户分类。这些类别本身可以进行分组和分类。
生成的结构可以表示为有向无环图(DAG),其中项目是图拓扑结构底部的汇点,而顶层类别是源头。请注意,尽管其中一些类别可能定义得很好,但很多都是用户定义的,可能非常混乱。
示例: (来源:theuprightape.net)
在该结构上,我想执行以下操作:
- 找到特定节点下方的所有项目(欧洲所有项目) - 找到通过n个节点集合的所有路径(如果有)(例如,通过SMTP从example.com发送的所有项目) - 找到位于一组节点下方的所有节点(交集:goyish brown foods)
第一个似乎很简单:从节点开始,沿着所有可能的路径到底部并收集那里的项目。然而,是否有更快的方法?记住我已经通过的节点可能有助于避免不必要的重复,但是否有更多的优化?
生成的结构可以表示为有向无环图(DAG),其中项目是图拓扑结构底部的汇点,而顶层类别是源头。请注意,尽管其中一些类别可能定义得很好,但很多都是用户定义的,可能非常混乱。
示例: (来源:theuprightape.net)
在该结构上,我想执行以下操作:
- 找到特定节点下方的所有项目(欧洲所有项目) - 找到通过n个节点集合的所有路径(如果有)(例如,通过SMTP从example.com发送的所有项目) - 找到位于一组节点下方的所有节点(交集:goyish brown foods)
第一个似乎很简单:从节点开始,沿着所有可能的路径到底部并收集那里的项目。然而,是否有更快的方法?记住我已经通过的节点可能有助于避免不必要的重复,但是否有更多的优化?
我该如何处理第二个问题?似乎第一步是确定集合中每个节点的高度,以确定从哪个节点开始,并找到包括剩余集合的所有路径。但这是最好的(或者甚至是一个好的)方法吗?
维基百科列出的图遍历算法似乎都关注于查找特定节点或两个节点之间最短或最有效的路径。我认为这两个都不是我想要的,还是我没有看到它如何适用于我的问题?我应该在哪里阅读?