数据分析之图算法: 基于Spark和Neo4j

31

第 4 章

路径查找算法和图搜索算法

图搜索算法对图的探究既可以是一般性发现，也可以是显式搜索。这些算法在图中构造路

径，但并不要求这些路径的计算性能最强。本章将介绍广度优先搜索和深度优先搜索，它

们既是遍历图的基础，也往往是各种分析的首要步骤。

路径查找算法基于图搜索算法，探索节点之间的路径，从某个节点开始遍历关系，直到抵

达目的地。这些算法用于识别图中的最优路径，可用于物流规划、最低成本呼叫或

IP

路

由、模拟博弈等。

具体来说，本章将介绍如下路径查找算法。



最短路径算法以及两个有用的变体

（

A*

算法和

Yen

算法

）

用于查找两个选定节点之间的最短路径。



所有点对最短路径算法和单源最短路径算法

用于查找所有节点对之间的最短路径或从选定节点到其他各节点的最短路径。



最小生成树算法

用于查找连通的树结构，保证从选定节点访问其他各节点的代价最小。



随机游走算法

这是对机器学习工作流程和其他图算法都很有用的预处理或采样步骤。

本章将介绍这些算法的运作原理，并给出相应的

Spark

示例和

Neo4j

示例。当算法仅在一

种平台上可用时，则仅提供一个示例或说明如何自定义实现。

32

｜

第

4

章

图

4-1

展示了这几种算法之间的关键区别，表

4-1

是每种算法及其示范用例的速查表。

图搜索算法

路径查找算法

随机路径查找算法

广度优先搜索 ...