Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

L'MFSet (Merge-Find Set), altrimenti conosciuto come struttura dati union-find, è una struttura dati derivante dal concetto di partizione, per cui dato un insieme finito di elementi a volte risulta utile partizionarli in insiemi disgiunti. L'algoritmo di Merge-Find è quindi utile per le due operazioni possibili su questa struttura dati:

• Ricerca: determina in quale insieme si trova un particolare elemento, o se due elementi appartengono allo stesso insieme
• Unione: combina o fonde due insiemi in un unico insieme

L'altra operazione su MFSet è Crea, tramite la quale è possibile dato un insieme crearne la partizione formata solo da singoletti. Con l'utilizzo di questi tre operatori è possibile risolvere molti problemi pratici.

• CREAMFSET (INSIEME) ${\displaystyle \rightarrow }$ MFSet
• TROVA (ELEMENTO, MFSET) ${\displaystyle \rightarrow }$ componente
• FONDI (ELEMENTO, ELEMENTO, MFSET) ${\displaystyle \rightarrow }$ MFSet

• CREAMFSET(${\displaystyle {\mathit {A))}$)=${\displaystyle {\mathit {S))}$

${\displaystyle {\mathit {S))}$ è quindi una famiglia di ${\displaystyle {\mathit {n))}$ = |${\displaystyle {\mathit {A))}$| componenti ${\displaystyle {\mathit {C_{1))))$,...,${\displaystyle {\mathit {C_{n))))$ ciascuno dei quali contiene un solo elemento di ${\displaystyle {\mathit {A))}$ tale che ${\displaystyle \bigcup _{i}^{n}{\mathit {C_{i))))$= ${\displaystyle {\mathit {A))}$.

• TROVA(${\displaystyle {\mathit {x)),{\mathit {S)))={\mathit {C))}$

se ${\displaystyle {\mathit {x))}$ appartiene ad una componente di ${\displaystyle {\mathit {S))}$ allora ${\displaystyle {\mathit {C))}$ è l'identificatore della componente cui ${\displaystyle {\mathit {x))}$ appartiene.

• FONDI(${\displaystyle {\mathit {x)),{\mathit {y)),{\mathit {S)))=S'}$

se TROVA(${\displaystyle {\mathit {x)),{\mathit {S)))}$ è diverso da ${\displaystyle TROVA({\mathit {y,S)))}$ quindi ${\displaystyle {\mathit {x))}$ ed ${\displaystyle {\mathit {y))}$ appartengono a componenti distinte di ${\displaystyle {\mathit {S))}$ allora ${\displaystyle {\mathit {S'))}$ è formato da tutte le componenti di ${\displaystyle {\mathit {S))}$ che non contengono ${\displaystyle {\mathit {x))}$ o ${\displaystyle {\mathit {y))}$, e da una nuova componente data dall'unione delle due componenti contenenti ${\displaystyle {\mathit {x))}$ ed ${\displaystyle {\mathit {y))}$.

Portale Informatica

Portale Matematica