Mfset

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( A {\displaystyle {\mathit {A}}} )= S {\displaystyle {\mathit {S}}}

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

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

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

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

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

Portale Informatica

Portale Matematica