• Versiones soportadas: Última (3.3) 3.2 3.1 3.0

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	TEXT	Edges SQL as described below.
Raíz	BIGINT	Identificador del vértice raíz del árbol. Cuando el valor es \(0\) se obtiene el bosque de expansión que comienza en nodos aleatorios para cada árbol del bosque.
Raíces	ARRAY[ANY-INTEGER]	Arreglo de identificadores de los vértices raíz. Valores \(0\) son ignorados Con el propósito de optimización, valores duplicados son ignorados.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

BFS optional parameters

Parámetro	Tipo	x Defecto	Descripción
max_depth	BIGINT	\(9223372036854775807\)	Upper limit of the depth of the tree. When negative throws an error.

Inner queries

Edges SQL

Columna	Tipo	x Defecto	Descripción
id	ANY-INTEGER		Identificador de la arista.
source	ANY-INTEGER		Identificador del primer vértice extremo de la arista.
target	ANY-INTEGER		Identificador del segundo vértice extremo de la arista.
cost	ANY-NUMERICAL		Weight of the edge (source, target)
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source) When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

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
seq	BIGINT	Valor secuencial a partir de \(1\).
depth	BIGINT	Profundidad del node. \(0\) when node = start_vid.
start_vid	BIGINT	Identificador del vértice raíz.
node	BIGINT	Identificador del node alcanzado usando edge.
edge	BIGINT	Identificador del edge utilizado para llegar a node. \(-1\) when node = start_vid.
cost	FLOAT	Costo por recorrer edge.
agg_cost	FLOAT	Costo agregado desde start_vid hasta node.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Ver también

• Árbol de expansión - Categoría

• Prim - Familia de funciones

• Las consultas utilizan la red Datos Muestra .

• Boost: Prim’s algorithm documentation

• Wikipedia: algoritmo de Prim

Índices y tablas

• Índice

• Página de Búsqueda