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

---

Puoimigliorare questa voce aggiungendo citazioni dafonti attendibili secondo lelinee guida sull'uso delle fonti.

L'MFSet (Merge-Find Set), altrimenti conosciuto come struttura datiunion-find, è unastruttura dati derivante dal concetto dipartizione, 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 \to }$ MFSet
• TROVA (ELEMENTO, MFSET)${\displaystyle \to }$ componente
• FONDI (ELEMENTO, ELEMENTO, MFSET)${\displaystyle \to }$ 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}}_{\mathit{1}}}$,...,${\displaystyle {\mathit{C}}_{\mathit{n}}}$ ciascuno dei quali contiene un solo elemento di${\displaystyle \mathit{A}}$ tale che${\displaystyle \bigcup _i^n{\mathit{C}}_{\mathit{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^{\prime }}$

se TROVA(${\displaystyle \mathit{x},\mathit{S})}$ è diverso da${\displaystyle TROVA(\mathit{y}\mathit{,}\mathit{S})}$ quindi${\displaystyle \mathit{x}}$ ed${\displaystyle \mathit{y}}$ appartengono a componenti distinte di${\displaystyle \mathit{S}}$ allora${\displaystyle {\mathit{S}}^{\prime }}$ è 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

• Strutture dati

• Senza fonti - programmazione
• Senza fonti - febbraio 2013