BFS - 类别

• pgr_kruskalBFS

• pgr_primBFS

使用广度优先搜索进行遍历。

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

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

• 当图连通时

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

• 当图不连通时

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

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

参数

参数	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述。
root vid	BIGINT	树的根顶点的标识符。 当值为 \(0\) 时，则获取从森林中每棵树的随机节点开始的生成森林。
root vids	ARRAY [ ANY-INTEGER ]	根顶点的标识符数组。 \(0\) 值被忽略 出于优化目的，任何重复的值都将被忽略。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

BFS可选参数

参数	类型	默认	描述
max_depth	BIGINT	\(9223372036854775807\)	树深度的上限。 为负数时抛出错误。

内部查询

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

结果列

返回一组 (seq, depth, start_vid, node, edge, cost, agg_cost)

参数	类型	描述
seq	BIGINT	从 \(1\) 开始的顺序值。
depth	BIGINT	node 的深度。 \(0\) 当 node = start_vid。
start_vid	BIGINT	根顶点的标识符。
node	BIGINT	使用 edge 到达的``node`` 的标识符。
edge	BIGINT	用于到达 node 的 edge 的标识符。 \(-1\) 当 node = start_vid。
cost	FLOAT	遍历 edge 的成本。
agg_cost	FLOAT	从 start_vid 到 node 的总成本。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

另请参阅

• Boost: Prim算法

• Boost: Kruskal算法

• 维基百科: Prim算法

• 维基百科: Kruskal算法

索引和表格

• Index

• Search Page