Kruskal - 函数族

• pgr_kruskal

• pgr_kruskalBFS

• pgr_kruskalDD

• pgr_kruskalDFS

Boost 图内部

描述

克鲁斯卡尔算法是一种贪婪的最小生成树算法，它在每个循环中查找并添加连接森林中任意两棵树的最小可能权重的边。

主要特点是：

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

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

• 当图连通时

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

• 当图不连通时

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

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

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

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

内部查询

列	类型	默认	描述
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

另请参阅

• 生成树 - 类别

• Boost: Kruskal算法

• 维基百科: Kruskal算法

索引和表格

• Index

• Search Page