Cvija Pošto ne mogu urediti, mislim da je ovdje došlo do zabune. Algoritam koji se koristi u zadacima je na 31 slajdu, to je onaj sa poljima, na 37 slajdu je sa stablima, možda sam tu pogriješio, ispričavam se na pogrešci.
saitama
Bobicki
member
Evo sad ću proći po algoritmu pa možda bude jasnije
Zadatak od kolege
member
Znači, na početku imamo ovakvo stanje
\begin{bmatrix}root && 1 && 2 && 3 && 4 && 5 && 6 \\
next && 1 && 2 && 3 && 4 && 5 && 6\\
length && 1 && 1 && 1 && 1 && 1 && 1\\
vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Sad radimo Union(1, 2)
Po algoritmu, xs = root(x) = root(1) = 1
ys = root(y) = root(2) = 2
xs i ys nisu jednaki pa provjeravamo njihove duljine (lenght)
ys nema veću duljinu od xs (obje su 1) pa znači da radimo sljedeći set komandi
length[xs] += length[ys]
root[ys] = xs
svi u polju u kojem je korijen bio ys, za korijen im postavi xs
na kraju zamijeni sljedećeg od xs i sljedećeg od ys
Nakon tog seta operacija se dobije
\begin{bmatrix}root && 1 && 1 && 3 && 4 && 5 && 6 \\
next && 2 && 1 && 3 && 4 && 5 && 6\\
length && 2 && 1 && 1 && 1 && 1 && 1\\
vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Onda ide Union(4, 3), isto sve
\begin{bmatrix}root && 1 && 1 && 4 && 4 && 5 && 6 \\
next && 2 && 1 && 4 && 3 && 5 && 6\\
length && 2 && 1 && 1 && 2 && 1 && 1\\
vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Nakon Union(2, 3) [xs = 1, ys = 4]:
\begin{bmatrix}root && 1 && 1 && 1 && 1 && 5 && 6 \\
next && 3 && 1 && 4 && 2 && 5 && 6\\
length && 4 && 1 && 1 && 2 && 1 && 1\\
vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Te na kraju nakon Union(1, 6)
\begin{bmatrix}root && 1 && 1 && 1 && 1 && 5 && 1 \\
next && 6 && 1 && 4 && 2 && 5 && 3\\
length && 5 && 1 && 1 && 2 && 1 && 1\\
vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Nacrtat se može pomoću ove tablice
