Versiones soportadas: Última (3.3) 3.2 3.1 3.0

`pgr_kruskal`¶

pgr_kruskal — Minimum spanning tree of a graph using Kruskal’s algorithm.

_images/boost-inside.jpeg — Boost Graph Inside¶

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 Kruskal.

Las características principales son:

Su implementación solo para grafo no direccionado.
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.

Se minimiza el peso total de todos los bordes del árbol o 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 (edge, cost)
OR EMPTY SET

Ejemplo: Minimum spanning forest

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`	Edges SQL as described below.

Consulta interna¶

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¶

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

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

Ver también¶

Árbol de expansión - Categoría
Kruskal - Familia de funciones
Las consultas utilizan la red Datos Muestra .
Boost: Kruskal’s algorithm
Wikipedia: algoritmo de Kruskal

Índices y tablas

pgr_kruskal¶