algorithm - prim - ¿Un algoritmo rápido para árboles de expansión mínima cuando las longitudes de los bordes están restringidas?

kruskal algorithm

Question

Supongamos que tiene un gráfico dirigido con longitudes de borde enteras no negativas que están en el rango de 0 a U - 1, inclusive. ¿Cuál es el algoritmo más rápido para calcular un árbol de expansión mínimo de este gráfico? Todavía podemos usar algoritmos de árbol de expansión mínimo existentes, como el algoritmo O (m log n) de Kruskal) o el algoritmo de Prim (O (m + n log n)). Sin embargo, para los casos en que U es pequeño, creo que debería ser posible hacerlo mucho mejor.

¿Hay algún algoritmo que sea competitivo con algoritmos MST más tradicionales que puedan explotar el hecho de que las longitudes de los bordes están restringidas para estar en algún rango?

¡Gracias!

Answer 1

Con los pesos de borde enteros puede usar el agrupamiento para lograr una cola de prioridad con la peor complejidad de O(1) , pero una complejidad adicional de espacio O(U) .

Dentro de los algoritmos MST que ha mencionado, debe poder reemplazar las colas de prioridad basadas en la comparación con esta estructura entera y, por lo tanto, eliminar la depenedencia O(log(n)) en los requisitos de complejidad. Espero que termines con una complejidad general en el estilo de O(n + m) .

Esencialmente configura un conjunto de listas de enlaces comprimidos, donde cada lista se indexa por el costo (entero) asociado con ese segmento:

struct bucket_list
{
    _cost; // array[0..N-1] holding current cost for each item

    _head; // array[0..U-1] holding index of first item in each bucket

    _next; // array[0..N-1] where _next[i] is the next item 
           // in a list for the ith item

    _prev; // array[0..N-1] where _prev[i] is the last item 
           // in a list for the ith item
};

Esta estructura se basa en el hecho de que cada elemento solo puede estar en una única lista de depósitos a la vez.

En función de esta estructura, puede lograr la peor complejidad O(1) para estas operaciones:

push(item, cost); // push an item onto the head of the appropriate bucket list

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list

update(item, old_cost, new_cost); // move an item between buckets by combining
                                  // push and _pop

Para usar esta estructura como una cola de prioridad, simplemente mantenga un índice apuntando al cubo mínimo actual para escanear. Cuando desee obtener el siguiente artículo de menor costo, simplemente extraiga el artículo principal de este segmento. Si la cubeta está vacía, aumenta el índice de la cubeta hasta que encuentre una que no esté vacía.

Por supuesto, si U vuelve muy grande, la complejidad del espacio adicional, y la posibilidad de una distribución dispersa de elementos sobre los cubos puede hacer que este tipo de enfoque no sea atractivo.

Answer 2

Fredman-Willard dio un algoritmo O (m + n) para las longitudes de los extremos enteros en la RAM de costo unitario.

Podría decirse que no es una gran mejora: sin la restricción en las longitudes de los bordes (es decir, las longitudes son un tipo de datos opaco que solo admite comparaciones), Chazelle dio un algoritmo O (m alfa (m, n) + n) (alfa es función inversa de Ackermann) y Karger-Klein-Tarjan dieron un algoritmo O (m + n) aleatorio.

No creo que la idea de Darren conduzca a un algoritmo O (m + n + U) -time. Jarnik ("Prim") no usa su cola de prioridad monótonamente, por lo que los segmentos pueden escanearse varias veces; Kruskal requiere una estructura de datos disjuntos, que no puede ser O (m + n).