Prim - Familia de funciones

_images/boost-inside.jpeg

Adentro: Boost Graph

Descripción

El algoritmo prim fue desarrollado en 1930 por el matemático checo Vojtěch Jarník. Es un algoritmo ambicioso que encuentra un árbol de expansión mínimo para un grafo ponderado no dirigido. Esto significa que encuentra un subconjunto de los bordes que forma un árbol que incluye cada vértice, donde se minimiza el peso total de todos los bordes del árbol. El algoritmo funciona creando este árbol un vértice a la vez, desde un vértice inicial arbitrario, paso a paso agregando la conexión más barata posible desde el árbol a otro vértice.

Estos algoritmos encuentran el bosque de expansión mínimo en un grafo posiblemente desconectado; en cambio, la forma más básica del algoritmo de Prim sólo encuentra árboles de expansión mínimos en los grafos conectados. Sin embargo, al ejecutar el algoritmo de Prim por separado para cada componente conectado del grafo, se denomina bosque de expansión mínimo.

Las principales características 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.

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

Nota

De boost Graph: «El algoritmo tal como se aplica en el Boost.Graph no produce resultados correctos en grafos con segmentos paralelos.»

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