Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5

pgr_strongComponents

pgr_strongComponents — 使用基于 DFS 的 Tarjan 算法构建有向图的强连通分量。

可用性

• 版本3.0.0

  • 结果列发生变化：

    • n_seq 被删除

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

  • Function promoted to official.

• 版本2.5.0

  • New experimental function.

描述

有向图的强连接组件是一组彼此可达的顶点。

主要特点是：

• 适用于 有向 图。

• 组件由顶点标识符描述。

• 返回值是有序的：

  • component 升序

  • node 升序

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

Boost Graph Inside

签名

pgr_strongComponents(Edges SQL)

返回集合 (seq, component, node)

OR EMPTY SET

示例:

图的重要组成部分

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

结果列

返回集合 (seq, component, node)

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

另请参阅

• 分量 - 函数族

• 示例数据

• Boost: Strong components

• 维基百科: 强连通分量

索引和表格

• Index

• Search Page