知识库

使用 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 过程 的路径扩展器过程来在扩展期间强制执行不同的唯一性配置。