Kruskal - Familia de funciones

_images/boost-inside.jpeg

Boost Graph Inside

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

Consulta interna

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

Ver también

Índices y tablas