pgr_prim

pgr_prim — 使用 Prim 算法的图的最小生成森林。

Boost 图内部

可用性

• 版本3.0.0

  • 官方 新函数

描述

该算法使用 Prim 算法在可能断开的图中找到最小生成森林。

主要特点是：

• 它的实现仅在 无向 图上。

• 仅在具有正成本的边进行处理。

• 当图连通时

  • 由此产生的边组成一棵树

• 当图不连通时

  • 为每个连通分量找到最小生成树。

  • 由此产生的边构成了一片森林。

• Prim运行时间： \(O(E * log V)\)

• 当图中没有边时，返回 EMPTY SET。

签名

总结

pgr_prim(Edges SQL)

返回 (edge, cost) 的集合

OR EMPTY SET

示例:

子图的最小生成森林

SELECT edge, cost FROM pgr_prim(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges WHERE id < 14'
) ORDER BY edge;
 edge | cost
------+------
    1 |    1
    2 |    1
    3 |    1
    4 |    1
    6 |    1
    7 |    1
    8 |    1
    9 |    1
   10 |    1
   12 |    1
   13 |    1
(11 rows)

参数

参数	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述。

内部查询

Edges SQL

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		边(source, target)的权重
reverse_cost	ANY-NUMERICAL	-1	边(target, source)的权重 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列

返回集合 (edge, cost)

列	类型	描述
edge	BIGINT	边的标识符。
cost	FLOAT	穿越边的成本。

另请参阅

• 生成树 - 类别

• Prim - 函数族

• 查询使用 示例数据 网络。

• Boost: Prim算法文档

• 维基百科: Prim算法

索引和表格

• Index

• Search Page