Un algoritmo veloce per alberi con spanning minimo quando le lunghezze degli spigoli sono vincolate?

Question

Supponiamo di disporre di un grafico diretto con lunghezze dei bordi non negative e intere comprese nell'intervallo da 0 a U - 1 incluso. Qual è l'algoritmo più veloce per calcolare un albero spanning minimo di questo grafico? Possiamo ancora utilizzare algoritmi di spanning tree minimi esistenti, come l'algoritmo O di Kruskal (m log n)) o l'algoritmo di Prim (O (m + n log n)). Tuttavia, per i casi in cui U è piccolo, penso che dovrebbe essere possibile fare molto meglio questo.

Esistono algoritmi che sono competitivi con algoritmi MST più tradizionali che sono in grado di sfruttare il fatto che le lunghezze dei bordi sono limitate in qualche intervallo?

Grazie!

Answer 1

Fredman-Willard ha fornito un algoritmo O (m + n) per le lunghezze dei fronti interi sulla RAM dei costi unitari.

Probabilmente non è un gran miglioramento: senza la restrizione sulle lunghezze degli spigoli (cioè le lunghezze sono un tipo di dati opaco che supporta solo i confronti), Chazelle ha dato un algoritmo O (m alfa (m, n) + n) (alfa è la funzione inversa di Ackermann) e Karger-Klein-Tarjan ha dato un algoritmo O (m + n) randomizzato.

Non credo che l'idea di Darren porti ad un algoritmo di tempo O (m + n + U). Jarnik ("Prim") non usa la sua coda di priorità monotonicamente, quindi i bucket possono essere scansionati più volte; Kruskal richiede una struttura di dati disgiunti, che non può essere O (m + n).

Answer 2

Con i pesi dei contatori interi è possibile utilizzare il benna per ottenere una coda di priorità con la complessità del caso peggiore O(1), ma ulteriore complessità dello spazio O(U).

All'interno degli algoritmi MST che hai menzionato dovresti essere in grado di sostituire le code di priorità basate sul confronto con questa struttura integer, e quindi rimuovere la depenenza O(log(n)) nei requisiti di complessità. Immagino che ti ritroverai con una complessità complessiva nello stile di O(n + m).

In sostanza si imposta una serie di compressi collegate liste, dove ogni lista è indicizzato dal costo associato a quel secchio (intero!):

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 
}; 

Questa struttura si basa sul fatto che ogni elemento può sii solo in una lista di secchi singoli contemporaneamente.

sulla base di questa struttura è possibile ottenere nel caso peggiore O(1) complessità di queste operazioni:

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 

Per utilizzare questa struttura come una coda di priorità è sufficiente mantenere un indice puntato verso il secchio minima corrente per eseguire la scansione. Quando vuoi ottenere il prossimo oggetto a minor costo, devi semplicemente estrarre l'elemento principale da questo bucket. Se il bucket è vuoto, incrementa l'indice del bucket finché non ne trovi uno non vuoto.

Ovviamente se U diventa molto grande, la complessità extra dello spazio e la possibilità di una distribuzione sparsa di articoli oltre i bucket possono rendere poco attraente questo tipo di approccio.