Kruskal - Familia de funciones¶

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 |
---|---|---|---|
|
ANY-INTEGER |
Identificador de la arista. |
|
|
ANY-INTEGER |
Identificador del primer vértice extremo de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice extremo de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Ver también¶
Índices y tablas