pgr_prim

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

_images/boost-inside.jpeg

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

穿越边的成本。

另请参阅

索引和表格