Prim - Familia de funciones

_images/boost-inside.jpeg

Boost Graph Inside

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 características principales son:

  • It’s implementation is only on undirected graph.

  • 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.

  • Prim’s running time: \(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 bordes paralelos «.

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