pgr_primBFS
¶
pgr_primBFS
— Algoritmo de Prim para el árbol de expansión mínimo con orden de primera búsqueda de profundidad.

Boost Graph Inside¶
Disponibilidad
Versión 3.0.0
Nueva función Oficial
Descripción¶
Visita y extrae la información de los nodos en el orden de búsqueda de Primera Búsqueda de Respiración del Árbol de Expansión Mínimo creado con el algoritmo de Prim.
Las características principales son:
It’s implementation is only on undirected graph.
El proceso se realiza sólo en las aristas con costos positivos.
Cuando el grafo es conectado
Las aristas resultantes componen un árbol
Cuando el grafo no está conectado,
Encuentra un árbol de expansión mínimo para cada componente conectado.
Las aristas resultantes conforman un bosque.
Prim’s running time: \(O(E * log V)\)
Los nodos de árbol devueltos desde un vértice raíz están en orden de la Primera Búsqueda de Anchura
Tiempo de ejecución de la Primera Búsqueda de Anchura: \(O(E + V)\)
Firmas¶
pgr_primBFS(Edges SQL, Root vid [, max_depth]) pgr_primBFS(Edges SQL, Root vids [, max_depth]) RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Un solo vértice¶
pgr_primBFS(Edges SQL, Root vid [, max_depth]) RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
- Ejemplo
El Árbol de Expansión Mínimo que tiene como vértice raíz \(2\)
SELECT * FROM pgr_primBFS(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
2
);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 2 | 2 | -1 | 0 | 0
2 | 1 | 2 | 1 | 1 | 1 | 1
3 | 1 | 2 | 3 | 2 | 1 | 1
4 | 1 | 2 | 5 | 4 | 1 | 1
5 | 2 | 2 | 4 | 3 | 1 | 2
6 | 2 | 2 | 6 | 5 | 1 | 2
7 | 2 | 2 | 8 | 7 | 1 | 2
8 | 2 | 2 | 10 | 10 | 1 | 2
9 | 3 | 2 | 9 | 9 | 1 | 3
10 | 3 | 2 | 11 | 11 | 1 | 3
11 | 3 | 2 | 7 | 6 | 1 | 3
12 | 3 | 2 | 13 | 14 | 1 | 3
13 | 4 | 2 | 12 | 13 | 1 | 4
(13 rows)
Múltiples vértices¶
pgr_primBFS(Edges SQL, Root vids [, max_depth]) RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
- Ejemplo
El Árbol de Expansión Mínimo que comienza en los vértices \(\{13, 2\}\) con \(depth <= 3\)
SELECT * FROM pgr_primBFS(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
ARRAY[13,2], max_depth := 3
);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 2 | 2 | -1 | 0 | 0
2 | 1 | 2 | 1 | 1 | 1 | 1
3 | 1 | 2 | 3 | 2 | 1 | 1
4 | 1 | 2 | 5 | 4 | 1 | 1
5 | 2 | 2 | 4 | 3 | 1 | 2
6 | 2 | 2 | 6 | 5 | 1 | 2
7 | 2 | 2 | 8 | 7 | 1 | 2
8 | 2 | 2 | 10 | 10 | 1 | 2
9 | 3 | 2 | 9 | 9 | 1 | 3
10 | 3 | 2 | 11 | 11 | 1 | 3
11 | 3 | 2 | 7 | 6 | 1 | 3
12 | 3 | 2 | 13 | 14 | 1 | 3
13 | 0 | 13 | 13 | -1 | 0 | 0
14 | 1 | 13 | 10 | 14 | 1 | 1
15 | 2 | 13 | 5 | 10 | 1 | 2
16 | 3 | 13 | 2 | 4 | 1 | 3
17 | 3 | 13 | 8 | 7 | 1 | 3
(17 rows)
Parámetros¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
Edges SQL as described below. |
|
Raíz |
|
Identificador del vértice raíz del árbol.
|
Raíces |
|
Arreglo de identificadores de los vértices raíz.
|
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
BFS optional parameters¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
\(9223372036854775807\) |
Upper limit of the depth of the tree.
|
Inner queries¶
Edges SQL¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ANY-INTEGER |
Identificador de la arista. |
|
|
ANY-INTEGER |
Identificador del primer vértice extremo de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice extremo de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Columnas de Resultados¶
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 |
|
|
Costo agregado desde |
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
Ver también¶
Las consultas utilizan la red Datos Muestra .
Índices y tablas