图数据库，第2版

第 7 章 用图形理论进行预测分析 利用图论进行预测分析

本作品已使用人工智能进行翻译。欢迎您提供反馈和意见：[e-mail]

在本章中，我们将研究一些处理图数据的分析技术和算法。图理论和图算法都是计算科学中成熟且广为人知的领域，我们将演示如何利用这两种方法从图数据库中挖掘复杂的信息。尽管具有计算科学背景的读者无疑会认识这些算法和技术，但本章的讨论并不涉及数学，以鼓励好奇的非专业人士深入了解。

深度优先和广度优先搜索

在了解高阶分析技术之前，我们需要重新熟悉一下基本的广度优先搜索算法，它是迭代整个图的基础。我们在本书中看到的大多数查询都是深度优先查询，而不是广度优先查询。也就是说，它们先从一个起点节点向外遍历到某个终点节点，然后再从同一个起点节点沿着不同的路径重复类似的搜索。当我们试图沿着一条路径发现离散的信息时，深度优先是一种很好的策略。

有信息的深度优先搜索

经典的深度优先算法搜索 是无信息的。也就是说，它只是搜索一条路径，直到找到图的终点。一旦到达终点，它就会回溯到起点节点，并尝试另一条路径。然而，由于图数据库语义丰富，我们可以提前结束沿着特定分支的搜索（例如，一旦我们发现一个节点没有兼容的传出关系，或者已经遍历了 "足够远的距离"）。这种知情搜索可以缩短执行时间。这正是前几章中 Cypher 查询和 Java 遍历所执行的搜索类型。

虽然我们使用深度优先搜索作为一般图遍历的基础策略，但许多有趣的算法都是以广度优先的方式遍历整个图的。也就是说，它们每次探索一层图，首先访问从起始节点开始的深度为 1 的每个节点，然后访问深度为 2 的每个节点，最后访问深度为 3 的节点，依此类推，直到访问完整个图为止。如图 7-1 所示，从标有O （表示原点）的节点开始，每次向外扩散一层，可以很容易地将这一过程可视化。

图 7-1. 广度优先搜索的过程

搜索的终止取决于正在执行的算法--大多数有用的算法都不是纯粹的广度优先搜索，而是在一定程度上进行了知情搜索。广度优先搜索通常用于路径搜索算法，或需要系统搜索整个图时（如我们在第 3 章中讨论的图全局算法）。

使用 Dijkstra 算法寻路

广度优先搜索是包括 Dijkstra 算法在内的众多经典图算法的基础。Dijkstra 算法（通常简称为 Dijkstra）用于寻找图中两个节点之间的最短路径。Dijkstra 算法非常成熟，1956 年就已发表，此后被计算机科学家广泛研究和优化。它的行为如下

1. 选取起点和终点节点，并将起点节点添加到已解节点集合（即已知从起点节点出发路径最短的节点集合）中，其值为 0（根据定义，起点节点与自身的路径长度为 0）。

2. 从起始节点开始，以广度为先遍历最近的邻居节点，并记录每个邻居节点的路径长度。

3. 取其中一个邻居的最短路径（如果出现并列，可任意选择），并将该节点标记为已解决，因为我们现在知道了从起始节点到该邻居的最短路径。

4. 从已求解的节点集合中，访问最近的邻居（注意先呼吸后前进），并记录从起始节点到这些新邻居的路径长度。不要访问任何已经解决的邻近节点，因为我们已经知道了到这些节点的最短路径。

5. 重复步骤 3 和 4，直到目的地节点被标记为已解决。

Dijkstra 算法的效率

Dijkstra 算法非常高效，因为它只计算图中可能路径中相对较小的一个子集的长度。当我们解决了一个节点后，从起始节点出发的最短路径就已知了，这样所有后续路径都可以安全地建立在这一知识之上。 ...