ScanImage010 (5)

i »-

i »-

WPROWADZENIE

W najbardziej nowocz.csnych komputerach możemy wykonywać dziesiątki lub setki milionów instrukcji na sekundę, więc koszt działania przedstawionego algorytmu nie będzie zauważalny dla małych m i n, ale może się okazać, że współczesne aplikacje wymagać będą analizowania miliardów obiektów i milionów par wejściowych. Nieodparcie nasuwa się więc konkluzja, że problemu połączeniowego nie można efektywnie rozwiązać za pomocą algorytmu szybkiego wyszukiwania (patrz zadanie 1.10). Procesem oceny wydajności i wyciągania takich wniosków zajmiemy się bardziej szczegółowo w rozdziale 2.

Na rysunku 1.4 pokazano graficzną reprezentację sytuacji z rysunku 1.3. Wybrane obiekty możemy potraktować jako reprezentantów zbiorów, do których należą, a wszystkie pozostałe jako wskazujące na reprezentanta odpowiedniego zbioru. Powód zastosowania graficznej reprezentacji tablicy stanie się niebawem jasny. Warto zauwa-

6) ® (o)    żyć, że połączenia między obiektami w tej reprezentacji

(|)    ($)    niekonieczne pokrywają się z rzeczywistymi połączeniami

par wejściowych - stanowią one jedynie te informacje,

które algorytm wybrał do zapamiętania i na podstawie których będzie w stanie ocenić, czy kolejne pary'- sąpołączone.

Kolejny algorytm, którym się zajmiemy, jest komplementarny względem poprzedniego. Nazwiemy go olgc-ryimem szybkiego scalania. Jest on oparty' na tej samej strukturze danych - tablicy' indeksowanej nazwami obick-

tów ale na innej interpretacji wartości elementów' tablicy, która prowadzi do bardziej złożonych struktur abstrakcyj-

nych. Każdy obiekt wskazuje na inny z tego samego zbioru

wyszukiwania za pomocą drzewa

Powyższy rysunek przedstawia graficzną reprezentację przykładu z rysunku 1.3. Połączenia między liczbami niekoniecznie reprezentują rzeczywiste połączenia obiektów wskazane za pomocą par wejściowych. Na przykład struktura u dołu ma połączenie 1-7, które nie zostało podane na wejściu, ale które istnieje ze względu na ciąg połączeń 7-3-4-9-5-6-1.

- struktury bez cykli. Aby stwierdzić, czy dwa obiekty

Rysunek 1.4

Reprezentacja szybkiego

należą do tego samego zbioru, należy od każdego z nich przejść ścieżką tworzoną przez kolejne wskaźniki, aż doj-

dzic się do obiektu wskazującego na siebie samego. Dwa obiekty należą do tego samego zbioru wtedy i tylko wtedy, gdy ten proces prowadzi je do tego samego obiektu końcowego. Jeżeli należą do różnych zbiorów', wędrówka od każdego z nich kończy się gdzie indziej (w innych obiektach wskazujących na siebie same). Aby scalić obiekty- (utworzyć sumę), należy .je po prostu połączyć jeden z tych obiektów' z drugim; stąd nazwa „szybkie scalanie’*.

Na rysunku 1.5 pokazano korespondującą z rysunkiem 1.4 graficzną reprezentację działania algorytmu szyb-