知识库

使用 Cypher 实现最长路径

虽然 Cypher 针对查找两个节点之间的最短路径（例如使用 shortestPath() 函数）进行了优化，但它没有类似的最长路径函数。在某些情况下，您可能需要查找最长路径，而不是最短路径。

树的根节点到叶节点

如果您有一个树状结构，想要查找根节点和叶节点之间的最长路径，并且不知道中间有多少个节点

MATCH p=(parent:Root)-[r:HAS_CHILD*1..10]->(child:Node)
RETURN p

这样做的问题是，它会为您提供所有路径，每跳一条，直到您到达叶节点。您想要的只是最长路径，以了解父节点和叶子节点是如何连接的。为了高效地完成此操作，请执行以下步骤：

MATCH p=(parent:Root)-[:HAS_CHILD*1..10]->(child:Node)
WHERE NOT (child)-[:HAS_CHILD]->()
RETURN p

以上查询的作用是：可变长度 1..10 将找到所有路径（应该只有一条），适用于任何最多跨越 10 跳的父子路径。WHERE 子句需要用于过滤路径，仅保留那些叶子节点没有传出 :HAS_CHILD 关系（即它找到链的末端）的路径。

存在多条路径时的最长路径

如果不使用非循环树结构，两个节点之间可能存在多条路径，您可能只想获取最长的一条。我们可以通过按路径长度排序并只取最长路径来实现这一点

MATCH p=(start:Node)-[:REL*1..10]->(end:Node)
WHERE id(start) = 123 AND id(end) = 456
RETURN p
ORDER BY length(p) DESC
LIMIT 1

提高查询效率的技巧

在一个连接良好的图谱中，像这样的变长路径查询可能会变得越来越昂贵。以下是一些保持其性能的技巧。

  1. 限制关系类型和方向 - 如果可能，只使用所需的类型，并使用有向关系。这可以减少扩展过程中遍历的路径数量。

  2. 为变长模式提供上限 - 在连接良好的图谱中，没有边界的模式可能会失控。设置上限有助于限制查询所需执行的工作。

  3. 在 MATCH 后面的 WHERE 子句中使用 all() 或 none() - 如果在扩展过程中需要评估谓词，并且它们必须应用于路径中的所有节点或关系，请在扩展期间对路径中的节点或关系使用 all() 或 none() 进行评估，而不是在找到所有路径后进行过滤。

  4. 在特殊情况或限制下使用 APOC 路径扩展器 - 对于某些限制，例如在扩展期间不重复节点，您可能希望使用来自 APOC 过程 的路径扩展器来强制执行扩展期间不同的唯一性配置。