• Supported versions:

pgr_prim

pgr_prim — Mínimo bosque de expansión de un grafo, utilizando el algoritmo de Prim.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0

    • Nueva función Oficial

Descripción

Este algoritmo encuentra el bosque de expansión mínimo en un grafo posiblemente desconectado usando el algoritmo de Prim.

Las principales características son:

  • Su implementación es solo para grafo no dirigido.

  • El proceso se realiza sólo en 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.

  • Tiempo de ejecución de Prim: \(O(E*log V)\)

  • EMPTY SET es regresado cuando no hay aristas en el grafo.

Firmas

Resumen

pgr_prim(SQL de aristas)
RETURNS SET OF (edge, cost)
OR EMPTY SET
Ejemplo:

Bosque de Expansión Mínimo de un subgrafo

SELECT edge, cost FROM pgr_prim(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges WHERE id < 14'
) ORDER BY edge;
 edge | cost
------+------
    1 |    1
    2 |    1
    3 |    1
    4 |    1
    6 |    1
    7 |    1
    8 |    1
    9 |    1
   10 |    1
   12 |    1
   13 |    1
(11 rows)

Parámetros

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas descritas más adelante.

Consultas Internas

SQL aristas

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

Peso de la arista (source, target)

reverse_cost

FLOTANTES

-1

Peso de la arista (target, source)

  • Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve CONJUNTO DE (edge, cost)

Columna

Tipo

Descripción

edge

BIGINT

Identificador de la arista.

cost

FLOAT

Coste para atravezar el borde.

Ver también

Índices y tablas