- MAKE-SET( $x$) creates a new set whose only member is pointed by $x$; Note that $x$ is not in the other sets.
- UNION( $x,y$) unites two dynamic sets containing objects $x$ and $y$, say ${S}_{x}$ and ${S}_{y}$, into a new set that ${S}_{x}\cup {S}_{y}$, assuming that ${S}_{x}\cap {S}_{y}=\varnothing $;
- FIND-SET( $x$) returns a pointer to the representative of the set containing $x$.
- INSERT( $a,S$) inserts an object $a$ to $S$, and returns $S\cup \{a\}$.
- DELETE( $a,S$) deletes an object $a$ from $S$, and returns $S-\{a\}$.
- SPLIT( $a,S$) partitions the objects of $S$ into two sets ${S}_{1}$ and ${S}_{2}$ such that ${S}_{1}=\{b\hspace{0.5em}|\hspace{0.5em}b\le a\hspace{0.5em}\&\hspace{0.5em}b\in S\}$, and ${S}_{2}=S-{S}_{1}$.
- MINIMUM( $S$) returns the minimum object in $S$.

- Connected components (CCs)
- Minimum Spanning Trees (MSTs)

CONNECTED-COMPONENTS $(G)$

1foreach $v\in V$

2doMAKE-SET $(v)$

3forevery edge $(u,v)\in E$

4doifFIND-SET $(u)$ $\ne $ FIND-SET $(v)$

5thenUNION $(u,v)$

SAME-COMPONENTS $(u,v)$

1ifFIND-SET $(u)$ $=$ FIND-SET $(v)$

2thenreturnTRUE

3returnFALSE

Edge processed | Collection of disjoint sets | |||||||||

initial sets | $\{a\}$ | $\{b\}$ | $\{c\}$ | $\{d\}$ | $\{e\}$ | $\{f\}$ | $\{g\}$ | $\{h\}$ | $\{i\}$ | $\{j\}$ |

$(b,d)$ | $\{a\}$ | $\{b,d\}$ | $\{c\}$ | $\{e\}$ | $\{f\}$ | $\{g\}$ | $\{h\}$ | $\{i\}$ | $\{j\}$ | |

$(e,g)$ | $\{a\}$ | $\{b,d\}$ | $\{c\}$ | $\{e,g\}$ | $\{f\}$ | $\{h\}$ | $\{i\}$ | $\{j\}$ | ||

$(a,c)$ | $\{a,c\}$ | $\{b,d\}$ | $\{e,g\}$ | $\{f\}$ | $\{h\}$ | $\{i\}$ | $\{j\}$ | |||

$(h,i)$ | $\{a,c\}$ | $\{b,d\}$ | $\{e,g\}$ | $\{f\}$ | $\{h,i\}$ | $\{j\}$ | ||||

$(a,b)$ | $\{a,b,c,d\}$ | $\{e,g\}$ | $\{f\}$ | $\{h,i\}$ | $\{j\}$ | |||||

$(e,f)$ | $\{a,b,c,d\}$ | $\{e,f,g\}$ | $\{h,i\}$ | $\{j\}$ | ||||||

$(b,c)$ | $\{a,b,c,d\}$ | $\{e,f,g\}$ | $\{h,i\}$ | $\{j\}$ |

MAKE-SET $({x}_{1})$,What's the total time complexity of the above operations?

MAKE-SET $({x}_{2})$,

$:$,

MAKE-SET $({x}_{n-1})$,

MAKE-SET $({x}_{n})$,

UNION $({x}_{1},{x}_{2})$,

UNION $({x}_{2},{x}_{3})$,

$:$,

UNION $({x}_{n-1},{x}_{n})$.

- union by rank.
- path compression

MAKE-SET $(x)$

1 $p[x]$$\leftarrow $$x$

2 $\mathrm{rank}[x]$$\leftarrow $$0$

FIND-SET $(x)$

1if$x\ne p[x]$

2then$p[x]$$\leftarrow $FIND-SET $(p[x])$

3return$p[x]$

UNION $(x,y)$

1 LINK( FIND-SET $(x)$, FIND-SET $(y)$)

LINK $(x,y)$where $\mathrm{rank}[x]$ is the height of $x$ in the tree. If both of the above methods are used together, the time complexity is $O(m\alpha (m,n))$.

1if$\mathrm{rank}[x]>\mathrm{rank}[y]$

2then$p[y]$$\leftarrow $$x$

3else$p[x]$$\leftarrow $$y$

4if$\mathrm{rank}[x]=\mathrm{rank}[y]$

5then$\mathrm{rank}[y]$$\leftarrow $$\mathrm{rank}[y]+1$

- $\mathrm{rank}[x]\le \mathrm{rank}[p[x]]$
- for any tree root $x$, $\mathrm{size}(x)\ge {2}^{\mathrm{rank}[x]}$ (Link operation)
- for any integer $r$, there are at most $n/{2}^{r}$ nodes of rank $r$
- each node has rank at most $\lfloor \mathrm{log}n\rfloor $, assuming there are at $n$ objects involved.

File translated from T

On 31 Mar 2006, 18:12.