1

我目前在 Java 中有一个仅附加的树数据结构。这棵树的主要目的是维护一个指向最长分支的指针。我通过引用最长分支中的最后一个节点来实现这一点，该最长分支在树中插入新节点时会更新。

出于性能和持久性的原因，我想使用 Neo4j Java API 将此实现移动到 Neo4j。在阅读文档时，我找不到一个方便的解决方案来查询 Neo4j 数据库中最长的分支。在我的实现中，我可以确保该图是一个 n 叉树。

在 Neo4j 中找到这种树中最长的分支的首选解决方案是什么？

  • 像在 Java 实现中那样保持指向最后一个节点的指针？
  • 塑造一个算法来找到最长的路径并使用遍历 API 或通过密码查询来实现它？
  • Neo4j 中的一些我还没有找到的内置功能？
4

1 回答 1

1

没有用于搜索最长路径的内置功能。

找到它的一种方法是找到根节点和叶节点之间的所有路径，然后按长度 desc 对它们进行排序。并采取第一个。

在cypher它应该用类似的东西来完成：

MATCH (root:Root)-[:HAS_CHILD*]->(n:Node)
WHERE size((n)-[:HAS_CHILD]->())=0
RETURN n
ORDER BY size(RELS(p)) DESC
LIMIT 1

一种更好的方法是通过遍历在一个动作中计算所有这些路径。APOC你可以用程序来看看apoc.path.expand。表现会更好。

最后一个解决方案是使用自定义遍历创建自己的算法，如果您已经找到最长的分支，则修剪分支。（可以通过自定义来完成Evaluator）。这种算法将比以前的解决方案具有更好的平均性能，但在最坏的情况下，复杂度是相同的。

就像你说的，你可以保留一个指向这个节点的指针。搜索它会非常快，但是当在你的树上完成写入时你必须维护这个指针（对写入性能有影响）。

选择权在您手中，取决于您想要达到的读写性能。

干杯

于 2017-07-11T10:25:21.923 回答