L'algoritmo di albero minimo di Sollin

Question

Sì, questo è i compiti. Mi chiedevo se qualcuno potesse spiegare il processo dell'algoritmo di Sollin (o Borůvka) per determinare un albero di spanning minimo. Inoltre, se potessi spiegare come determinare il numero di iterazioni nel peggiore dei casi, sarebbe fantastico.

Answer 1

Al livello superiore, l'algoritmo funziona come segue:

• Mantieni di avere un certo numero di alberi da spanning per alcuni sottgrafi. Inizialmente, ogni vertice del grafico è un MST senza bordi.
• In ogni iterazione, per ciascuno dei tuoi alberi che attraversa, trova un bordo più economico che lo collega a un altro albero che attraversava. (Questa è una semplificazione.)

Il caso peggiore in termini di iterazioni è che unisce sempre coppie di alberi. In tal caso, il numero di alberi che hai si dimezzerà in ogni iterazione, quindi il numero di iterazioni è logaritmico nel numero di nodi.

Si noti inoltre che c'è un trucco speciale coinvolto nella scelta dei bordi da aggiungere: se non stavi attento, potresti introdurre un cerchio quando l'albero A si collega all'albero B, all'albero B si collega all'albero C e all'albero C si collega all'albero A. ( Questo può accadere solo se tutti e tre i bordi scelti hanno lo stesso peso. Il trucco è avere un tie-rompicapo arbitrario ma fisso, come un ordine fisso dei bordi.)

Quindi lì, questa è la mia panoramica sul retro-indice.

Answer 2

Sto usando la terminologia del laico.

• Prima seleziona un vertice
• Controlla tutti i bordi da quel vertice e seleziona uno con il peso minimo
• Fallo per tutti i vertici (alcuni bordi possono essere selezionati più di una volta)
• Otterrai componenti connessi.
• Da questi componenti collegati selezionare un bordo con peso minimo.

Si formerà il tuo albero da spanning con peso minimo