Prim - 函数族

• pgr_prim

• pgr_primBFS

• pgr_primDD

• pgr_primDFS

Boost 图内部

描述

prim 算法由捷克数学家 Vojtěch Jarník 于 1930 年开发。 它是一种贪心算法，为带权无向图找到最小生成树。 这意味着它找到形成包含每个顶点的树的边的子集，其中树中所有边的总权重最小化。 该算法的运行方式是从任意起始顶点一次构建一个顶点，在每一步添加从树到另一个顶点的最便宜的可能连接。

该算法在可能不连通的图中找到最小生成森林； 相反，Prim 算法的最基本形式只能在连通图中找到最小生成树。 然而，对图的每个连通分量分别运行Prim算法，则称为最小生成森林。

主要特点是：

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

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

• 当图连通时

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

• 当图不连通时

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

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

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

Note

来自 boost Graph：“Boost.Graph 中实现的算法不会在具有平行边的图上产生正确的结果。”

内部查询

列	类型	默认	描述
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: Prim算法

• 维基百科: Prim算法

索引和表格

• Index

• Search Page