Kruskal - Familia de funciones

_images/boost-inside.jpeg

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

Índices y tablas