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

pgr_kruskal

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

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

Las características principales 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.

• 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(SQL de aristas)

RETURNS SET OF (edge, cost)

OR EMPTY SET

Ejemplo:

Bosque de expansión mínimo

SELECT * FROM pgr_kruskal(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges 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
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

• Árbol de expansión - Categoría

• Kruskal - Familia de funciones

• Las consultas utilizan la red Datos Muestra .

• Boost: algoritmo de Kruskal

• Wikipedia: algoritmo de Kruskal

Índices y tablas

• Índice

• Página de Búsqueda