Mfset

Da Wikipedia, l'enciclopedia libera.

L'MFSet (Merge-Find Set), altrimenti conosciuto come struttura dati union-find, è una struttura dati derivante dal concetto di Insieme delle parti, 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 è CreaMFSet tramite la quale è possibile dato un insieme crearne l'insieme delle parti di ciascun elemento. Con l'utilizzo di questi tre operatori è possibile risolvere molti problemi pratici.

Operatori[modifica | modifica sorgente]

Sintassi[modifica | modifica sorgente]

  • CREAMFSET (INSIEME) \rightarrow MFSet
  • TROVA (ELEMENTO, MFSET) \rightarrow componente
  • FONDI (ELEMENTO, ELEMENTO, MFSET) \rightarrow MFSet

Semantica[modifica | modifica sorgente]

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

\mathit{S} è quindi una famiglia di \mathit{n} = |\mathit{A}| componenti \mathit{C_1},...,\mathit{C_n} ciascuno dei quali contiene un solo elemento di \mathit{A} tale che \bigcup_i^{n} \mathit{C_i}= \mathit{A}.

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

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

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

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