Rilasciato · in miglioramento
Algorithm
Union-Find (insiemi disgiunti) tiene gli elementi in gruppi non sovrapposti e unisce gruppi o verifica l'appartenenza in tempo quasi costante.
Union-Find, detta anche struttura dati per insiemi disgiunti, gestisce una collezione di elementi suddivisa in insiemi che non si sovrappongono. Offre solo due operazioni: find restituisce il rappresentante dell'insieme a cui appartiene un elemento, mentre union fonde gli insiemi di due elementi. Ogni insieme è memorizzato come un albero di puntatori al padre, la cui radice è il rappresentante.
Quando i collegamenti vengono solo aggiunti e bisogna chiedersi più volte se due elementi sono connessi, Union-Find è molto più veloce che visitare il grafo ogni volta. Con la compressione dei cammini e l'unione per rango o dimensione, il costo ammortizzato per operazione scende alla funzione di Ackermann inversa α(n), che non supera 4 per nessun input realistico. È lo strumento standard dietro l'albero ricoprente minimo di Kruskal, il rilevamento di cicli, le componenti connesse e i problemi di raggruppamento come l'unione di account, ed è un tema frequente nei colloqui tecnici.
Inizia implementando find e union su un unico array parent e segui a mano come un albero degenera in una catena senza ottimizzazioni. Poi aggiungi l'unione per dimensione e la compressione dei cammini una alla volta, osservando come cambia la profondità degli alberi. Infine risolvi problemi di componenti connesse, rilevamento di cicli e Kruskal per abituarti a sfruttare il valore restituito da union.
find risale i puntatori al padre fino alla radice, il rappresentante, e union appende una radice sotto l'altra per fondere due insiemi.
find collega direttamente alla radice i nodi visitati e appiattisce l'albero, così le chiamate successive sono più rapide.
Appendere l'albero più piccolo sotto quello più grande mantiene l'altezza di ogni albero entro log n.
Con entrambe le ottimizzazioni, m operazioni richiedono O(m α(n)), e la funzione di Ackermann inversa α(n) vale al massimo 4 nella pratica.
La classe DSU memorizza gli insiemi in due array, parent e size. find risale i puntatori e usa il dimezzamento del cammino, collegando ogni nodo al nonno, per mantenere gli alberi bassi. union appende l'insieme più piccolo sotto quello più grande e restituisce False se i due elementi sono già nello stesso insieme. L'esempio unisce sei elementi in tre gruppi e stampa verifiche di appartenenza e il numero di insiemi.
union_find.py
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
dsu.union(a, b)
print(dsu.find(2) == dsu.find(0)) # True
print(dsu.find(4) == dsu.find(5)) # False
print(len({dsu.find(x) for x in range(6)})) # 3
python union_find.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Union-Find.
Fai domande, condividi la tua esperienza e scambia opinioni su Union-Find.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.