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 solo está en el grafo no direccionado.

• El proceso se realiza sólo en las aristas con costos positivos.

• Se minimiza el peso total de todos los bordes del árbol o bosque.

• Cuando el grafo está 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.

• Tiempo de ejecución de Kruskal: \(O(E * log E)\)

Consulta interna

Columna	Tipo	Valores predeterminados	Descripción
id	ANY-INTEGER		Identificador de la arista.
origen	ANY-INTEGER		Identificador del primer punto final en el vértice de la arista.
objetivo	ANY-INTEGER		Identificador del segundo punto final en el vértice de la arista.
cost	ANY-NUMERICAL		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	ANY-NUMERICAL	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Ver también

• Árbol de expansión - Categoría

• Boost: algoritmo de documentación de Kruskal

• Wikipedia: algoritmo de Kruskal

Índices y tablas

• Índice

• Página de Búsqueda