pgr_biconnectedComponents

pgr_biconnectedComponents — 无向图的双连通分量。

Boost 图内部

可用性

• 版本3.0.0

  • 结果列发生变化：

    • n_seq 被删除

    • seq 将类型更改为``BIGINT``

  • 官方 函数

• 版本2.5.0

  • 新 实验 函数

描述

无向图的双连通分量是顶点的最大子集，因此从特定分量中删除顶点不会断开该分量。 与连接组件不同，顶点可以属于多个双连接组件。 顶点可以存在于多个双连通分量中，但每条边只能包含在单个双连通分量中。

主要特点是：

• 适用于 无向 图。

• 组件由边描述。

• 返回值是有序的：

  • component 升序。

  • edge 升序。

• 运行时间： \(O(V + E)\)

签名

pgr_biconnectedComponents(Edges SQL)

Returns set of (seq, component, edge)

OR EMPTY SET

示例:

图的双连通分量

SELECT * FROM pgr_biconnectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | edge
-----+-----------+------
   1 |         1 |    1
   2 |         2 |    2
   3 |         2 |    3
   4 |         2 |    4
   5 |         2 |    5
   6 |         2 |    8
   7 |         2 |    9
   8 |         2 |   10
   9 |         2 |   11
  10 |         2 |   12
  11 |         2 |   13
  12 |         2 |   15
  13 |         2 |   16
  14 |         6 |    6
  15 |         7 |    7
  16 |        14 |   14
  17 |        17 |   17
  18 |        18 |   18
(18 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

结果列

Returns set of (seq, component, edge)

列	类型	描述
seq	BIGINT	从 1 开始的顺序值。
component	BIGINT	分量标识符。 具有组件中最小边标识符的值。
edge	BIGINT	属于该 分量 的边的标识符。

另请参阅

• 分量 - 函数族

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

• Boost: 双连通分量

• 维基百科: 双连通分量

索引和表格

• Index

• Search Page