pgr_kruskal
¶
pgr_kruskal
— Minimum spanning tree of a graph using Kruskal’s algorithm.

Boost Graph Inside¶
Disponibilidad
Versión 3.0.0
Nueva función Oficial
Descripción¶
Este algoritmo encuentra el bosque de expansión mínimo en un grafo posiblemente desconectado usando el algoritmo de Kruskal.
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)\)
EMPTY SET es regresado cuando no hay aristas en el grafo
Firmas¶
Resumen
pgr_kruskal(Edges SQL) RETURNS SET OF (edge, cost) OR EMPTY SET
- Ejemplo
Minimum spanning forest
SELECT * FROM pgr_kruskal(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table ORDER BY id'
) ORDER BY edge;
edge | cost
------+------
1 | 1
2 | 1
3 | 1
6 | 1
7 | 1
10 | 1
11 | 1
12 | 1
13 | 1
14 | 1
15 | 1
16 | 1
17 | 1
18 | 1
(14 rows)
Parámetros¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
Edges SQL as described below. |
Consulta interna¶
Edges SQL¶
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
Columnas de Resultados¶
Devuelve SET OF (conjunto de) (edge, cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador de la arista. |
|
|
Coste para atravezar el borde. |
Ver también¶
Las consultas utilizan la red Datos Muestra .
Índices y tablas