pgr_kruskal

pgr_kruskal — 使用 Kruskal 算法的图的最小生成树。

Boost 图内部

可用性

• 版本3.0.0

  • 官方 新函数

描述

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

主要特点是：

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

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

• 当图连通时

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

• 当图不连通时

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

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

• 树或森林中所有边的总权重最小化。

• 克鲁斯卡尔的运行时间： \(O(E * log E)\)

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

签名

总结

pgr_kruskal(Edges SQL)

返回 (edge, cost) 的集合

OR EMPTY SET

示例:

最小生成森林

SELECT * FROM pgr_kruskal(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges ORDER BY id'
) ORDER BY edge;
 edge | cost
------+------
    1 |    1
    2 |    1
    3 |    1
    6 |    1
    7 |    1
   10 |    1
   11 |    1
   12 |    1
   13 |    1
   14 |    1
   15 |    1
   16 |    1
   17 |    1
   18 |    1
(14 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	穿越边的成本。

另请参阅

• 生成树 - 类别

• Kruskal - 函数族

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

• Boost: Kruskal算法

• 维基百科: Kruskal算法

索引和表格

• Index

• Search Page