pgr_depthFirstSearch
- Proposed¶
pgr_depthFirstSearch
— Devuelve un recorrido de búsqueda de profundidad del grafo. El grafo puede ser dirigido o no dirigido.

Adentro: Boost Graph¶
Advertencia
Funciones propuestas para la próxima versión mayor.
No están oficialmente en la versión actual.
Es probable que oficialmente formen parte del próximo lanzamiento:
Las funciones hacen uso de ENTEROS y FLOTANTES
Es posible que el nombre no cambie. (Pero todavía puede)
Es posible que la firma no cambie. (Pero todavía puede)
Es posible que la funcionalidad no cambie. (Pero todavía puede)
Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.
Es posible que la documentación necesite un refinamiento.
Disponibilidad
Versión 3.3.0
Promovido a función propuesta
Versión 3.2.0
New experimental signatures:
pgr_depthFirstSearch
(Single Vertex)pgr_depthFirstSearch
(Multiple Vertices)
Descripción¶
El algoritmo de Primera Búsqueda de Profundidad es un algoritmo de recorrido que comienza desde un vértice raíz, va lo más profundo posible y retrocede una vez que se alcanza un vértice sin vértices adyacentes o con todos los vértices adyacentes visitados. El recorrido continúa hasta que se visitan todos los vértices accesibles desde el vértice raíz.
Las características principales son:
La implementación funciona para los grafos dirigidos y no dirigidos.
Proporciona la orden del recorrido de Primera Búsqueda de Profundidad desde un vértice raíz o desde un conjunto de vértices raíz.
Un parámetro opcional de profundidad máxima no negativo para limitar los resultados hasta una profundidad particular.
Para fines de optimización, se omiten los valores duplicados en los Root vids.
No produce la ruta más corta desde un vértice de origen a un vértice de destino.
No se garantiza que el coste agregado del recorrido sea mínimo.
Los valores devueltos se ordenan en orden ascendente de start_vid.
Tiempo de ejecución de la Primera Búsqueda de Profundidad: \(O(E + V)\)
Firmas¶
Resumen
pgr_depthFirstSearch(Edges SQL, Root vid [, directed] [, max_depth]) pgr_depthFirstSearch(Edges SQL, Root vids [, directed] [, max_depth]) RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Vértice único¶
pgr_depthFirstSearch(Edges SQL, Root vid [, directed] [, max_depth]) RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
- Ejemplo:
From root vertex \(6\) on a directed graph with edges in ascending order of
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)
Múltiples vértices¶
pgr_depthFirstSearch(Edges SQL, Root vids [, directed] [, max_depth]) RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
- Ejemplo:
From root vertices \(\{12, 6\}\) on an undirected graph with depth \(<= 2\) and edges in ascending order of
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)
Parámetros¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
SQL Aristas descritas más adelante. |
|
Raíz |
|
Identificador del vértice raíz del árbol.
|
Raíces |
|
Arreglo de identificadores de los vértices raíz.
|
Donde:
- ENTEROS:
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC:
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
Parámetros opcionales¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
DFS optional parameters¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
\(9223372036854775807\) |
Upper limit of the depth of the tree.
|
Consultas internas¶
SQL de aristas¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Return columns¶
Regresa SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Parámetro |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de \(1\). |
|
|
Profundidad del
|
|
|
Identificador del vértice raíz. |
|
|
Identificador del |
|
|
Identificador del
|
|
|
Costo por recorrer |
|
|
Coste agregado desde |
Donde:
- ENTEROS:
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC:
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
Ejemplos Adicionales¶
- Ejemplo:
Same as Single vertex but with edges in descending order of
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)
El recorrido resultante es diferente.
The left image shows the result with ascending order of ids and the right image shows with descending order of the edge identifiers.
Ver también¶
Boost: Documentación del algoritmo de Primera Búsqueda de Profundidad
“Wikipedia: Algoritmo de la Primera Búsqueda de Profundidad <https://en.wikipedia.org/wiki/Depth-first_search>`__
Índices y tablas