pgr_kruskal

pgr_kruskal — Devuelve el árbol de expansión mínimo del grafo utilizando el algoritmo Kruskal.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0
    • Nueva función Oficial

Soporte

Descripción

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

Las características principales son:

  • Su implementación solo está en el grafo no direccionado.
  • El proceso se realiza sólo en las aristas con costos positivos.
  • Se minimiza el peso total de todos los bordes del árbol o bosque.
  • Cuando el grafo está 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 Kruskal: \(O(E * log E)\)
  • EMPTY SET es regresado cuando no hay aristas en el grafo

Firmas

Resumen

pgr_kruskal(edges_sql)

RETURNS SET OF (seq, edge, cost)
OR EMPTY SET
Ejemplo:Bosque de expansión mínimo 
SELECT * FROM pgr_kruskal(
    'SELECT id, source, target, cost, reverse_cost
        FROM edge_table ORDER BY id'
) ORDER BY edge;
 edge | cost
------+------
    1 |    1
    2 |    1
    3 |    1
    6 |    1
    7 |    1
   10 |    1
   11 |    1
   12 |    1
   13 |    1
   14 |    1
   15 |    1
   16 |    1
   17 |    1
   18 |    1
(14 rows)

Parámetros

Parámetro Tipo Descripción
Edges SQL TEXT Consulta SQL descrita en Inner query.

Consulta interna

Columna Tipo Valores predeterminados Descripción
id ANY-INTEGER   Identificador de la arista.
origen ANY-INTEGER   Identificador del primer punto final en el vértice de la arista.
objetivo ANY-INTEGER   Identificador del segundo punto final en el vértice de la arista.
cost ANY-NUMERICAL  

Peso de la arista (source, target)

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

Peso de la arista (target, source),

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

Donde:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve SET OF (conjunto de) (edge, cost)

Columna Tipo Descripción
edge BIGINT Identificador de la arista.
cost FLOAT Coste para atravezar el borde.