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:
Nota
De boost Graph: «El algoritmo tal como se aplica en el Boost.Graph no produce resultados correctos en grafos con bordes paralelos «.
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)
|
|
reverse_cost | ANY-NUMERICAL |
-1 | Peso de la arista (target, source),
|
Donde:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Índices y tablas