`pgr_depthFirstSearch` - 拟议¶

pgr_depthFirstSearch — 返回图的深度优先搜索遍历。该图可以是有向图或无向图。

Warning

下一版本的拟议功能。

它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分：
- 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名字可能不会改变。（但仍然有可能改变）
- 签名可能不会改变。（但仍然有可能改变）
- 功能可能不会改变。（但仍然有可能改变）
- pgTap 测试已经完成。但可能需要更多。
- 文档可能需要完善。

可用性

版本 3.3.0
- 升级至拟议函数
版本3.2.0
- 新实验签名：
  - pgr_depthFirstSearch (单个顶点)
  - pgr_depthFirstSearch (多个顶点)

描述¶

深度优先搜索算法是一种遍历算法，从根顶点开始，尽可能深入探索，一旦到达一个没有相邻顶点或所有相邻顶点都已访问的顶点，就会回溯。遍历会一直持续，直到从根顶点可达的所有顶点都被访问。

主要特点是：

该实现适用于有向图和无向图。
提供从根顶点或一组根顶点开始的深度优先搜索遍历顺序。
可选的非负最大深度参数，用于限制结果的深度到特定的深度。
为了优化的目的，Root vids 中的任何重复值都会被忽略。
它不会生成从根顶点到目标顶点的最短路径。
不保证遍历的总成本最小。
返回值按 start_vid 升序排列。
深度优先搜索运行时间： \(O(E + V)\)

签名¶

总结

pgr_depthFirstSearch(Edges SQL, root vid, [options])
pgr_depthFirstSearch(Edges SQL, root vids, [options])
options: [directed, max_depth]

返回 (seq, depth, start_vid, node, edge, cost, agg_cost) 的集合

单顶点¶

pgr_depthFirstSearch(Edges SQL, root vid, [options])

options: [directed, max_depth]

返回 (seq, depth, start_vid, node, edge, cost, agg_cost) 的集合

示例:: 从根顶点 \(6\) 开始，该顶点位于一个有向图中，其边按 id 升序排列

SELECT * FROM pgr_depthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges
  ORDER BY id',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |    7 |    4 |    1 |        1
   4 |     2 |         6 |    3 |    7 |    1 |        2
   5 |     3 |         6 |    1 |    6 |    1 |        3
   6 |     2 |         6 |   11 |    8 |    1 |        2
   7 |     3 |         6 |   16 |    9 |    1 |        3
   8 |     4 |         6 |   17 |   15 |    1 |        4
   9 |     4 |         6 |   15 |   16 |    1 |        4
  10 |     5 |         6 |   10 |    3 |    1 |        5
  11 |     3 |         6 |   12 |   11 |    1 |        3
  12 |     2 |         6 |    8 |   10 |    1 |        2
  13 |     3 |         6 |    9 |   14 |    1 |        3
(13 rows)

多个顶点¶

pgr_depthFirstSearch(Edges SQL, root vids, [options])

options: [directed, max_depth]

返回 (seq, depth, start_vid, node, edge, cost, agg_cost) 的集合

示例:: 从根顶点开始 \({12, 6\}\) 在一个无向图上，depth \(<=2\)，边按 id 升序排列

SELECT * FROM pgr_depthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges
  ORDER BY id',
  ARRAY[12, 6], directed => false, max_depth => 2);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |   10 |    2 |    1 |        1
   4 |     2 |         6 |   15 |    3 |    1 |        2
   5 |     2 |         6 |   11 |    5 |    1 |        2
   6 |     1 |         6 |    7 |    4 |    1 |        1
   7 |     2 |         6 |    3 |    7 |    1 |        2
   8 |     2 |         6 |    8 |   10 |    1 |        2
   9 |     0 |        12 |   12 |   -1 |    0 |        0
  10 |     1 |        12 |   11 |   11 |    1 |        1
  11 |     2 |        12 |   10 |    5 |    1 |        2
  12 |     2 |        12 |    7 |    8 |    1 |        2
  13 |     2 |        12 |   16 |    9 |    1 |        2
  14 |     1 |        12 |    8 |   12 |    1 |        1
  15 |     2 |        12 |    9 |   14 |    1 |        2
  16 |     1 |        12 |   17 |   13 |    1 |        1
(16 rows)

参数¶

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

参数

类型

描述

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

可选参数¶

列	类型	默认	描述
`directed`	`BOOLEAN`	`true`	当 `true` 时，该图被视为有有向如果为 `false` ，则该图被视为无向。

DFS 可选参数¶

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

参数

类型

默认

描述

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

其他示例¶

示例:: 与单顶点相同，但边按 id 降序排列。

SELECT * FROM pgr_depthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges
  ORDER BY id DESC',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    7 |    4 |    1 |        1
   3 |     2 |         6 |    8 |   10 |    1 |        2
   4 |     3 |         6 |    9 |   14 |    1 |        3
   5 |     3 |         6 |   12 |   12 |    1 |        3
   6 |     4 |         6 |   17 |   13 |    1 |        4
   7 |     5 |         6 |   16 |   15 |    1 |        5
   8 |     6 |         6 |   15 |   16 |    1 |        6
   9 |     7 |         6 |   10 |    3 |    1 |        7
  10 |     8 |         6 |   11 |    5 |    1 |        8
  11 |     2 |         6 |    3 |    7 |    1 |        2
  12 |     3 |         6 |    1 |    6 |    1 |        3
  13 |     1 |         6 |    5 |    1 |    1 |        1
(13 rows)

由此产生的遍历是不同的。

左图显示的是按 ID 升序排列的结果，右图显示的是按边缘标识符降序排列的结果。

另请参阅¶

索引和表格

pgr_depthFirstSearch - 拟议¶

描述¶

签名¶

单顶点¶

多个顶点¶

参数¶

可选参数¶

DFS 可选参数¶

内部查询¶

Edges SQL¶

结果列¶

其他示例¶

另请参阅¶

`pgr_depthFirstSearch` - 拟议¶