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

58

｜

第

4

章

捷克科学家

Otakar Bor

ů

vka

于

1926

年首次提出最小加权生成树算法。诞生于

1957

年的

Prim

算法，是最简单、最著名的最小生成树算法。

Prim

算法与

Dijkstra

最短路径算法类似，但它并没有在每个关系结束时都最小化总路径长度，

而是将每个关系的长度分别最小化。与

Dijkstra

算法不同，它允许计算带有负权重的关系。

最小生成树算法的流程如图

4-10

所示。

图 4-10：最小生成树算法的步骤

步骤如下。

1.

算法从只包含一个节点的树开始。在图

4-10

中，它是从节点

A

开始的。

2.

选择从该节点出发权重最小的关系并将其（连同与之关联的节点）添加到树中。在本例

中为

A-D

。

3.

重复此过程，始终选择权重最小且所连接节点尚不在树中的关系。如果将本例与图

4-9

中的单源最短路径算法示例进行比较，就会发现第

4

张图中的路径有所不同。这是因为

单源最短路径算法基于从根节点开始的总累计值来计算最短路径，而最小生成树只考虑

下一步的代价。

4.

当再没有更多节点要添加时，当前树即为最小生成树。

该算法也有许多变体，可以查找最大权重生成树（代价最大的树）和

k

生成树（限制树的

规模）。

4.7.1

　何时使用最小生成树算法

当需要查找经过所有节点的最佳路径时，请使用最小生成树。因为路径是根据每一步的代

价来选择的，所以在一次行程中必须经过所有节点时，该算法非常有用。（如果不需要一

条单次行程的路径，请参阅

4.6

节 。）

该算法既可用于优化连通系统（如水管和电路设计）的路径，也可用于近似求解一些计算

时间未知的问题，比如旅行商问题和某些类型的舍入问题。虽然不一定总能找到绝对最优 ...