Kruskal - Familia de funciones

• pgr_kruskal

• pgr_kruskalBFS

• pgr_kruskalDD

• pgr_kruskalDFS

Adentro: Boost Graph

Descripción

Kruskal es un ambicioso algoritmo para generar un árbol de expansión mínimo que en cada ciclo encuentra y agrega la arista del menor peso posible que conecta dos árboles en el bosque.

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)\)

Consultas Internas

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

Ver también

• Árbol de expansión - Categoría

• Boost: algoritmo de Kruskal

• Wikipedia: algoritmo de Kruskal

Índices y tablas

• Índice

• Página de Búsqueda