ScanImage009 (5)

1.3. ALGORYTMY WYSZUKIWANIA I SCALANIA m» a®? ras sra    .<5%; :•*

Program 1.1. Rozwiązanie problemu połączeniowego.

Algorytm szybkiego wyszukiwania

Poniższy program odczytuje ze standardowego wejścia sekwencję par liczb całkowitych nieujemnych mniejszych niż n (parę p-q należy interpretować jako zdanie obiekt p jest połączony z obiektem q”) i drukuje na wyjściu paty reprezentujące obiekty, które jeszcze nie są połączone. W programie zdefiniowano tablicę id, zawierającą po jednym elemencie dla każdego obiektu. Tablica ma własność taką, że id [ p ] i id 1 q] są równe wtedy i tylko wtedy, gdy p i q są połączone. Dla uproszczenia n zdefiniujemy jako stałą. Możemy ją ewentualnie pobrać na wejściu i miejsce w pamięci przeznaczone na tablice id rezerwować dynamicznie (patrz podrozdział 3.2).

łinclude ciostream.h> static const int n - 10000; int main ()

{ int i, p, q, idfn];

for (i = C; i < n; i++) id[i) = i; while (cir. » p » q)

\ int t = id[p];

if (t == id[q]) continue;

for (i =0; i < n; i++)

if (id[i] — t> id[i] = id[ql;

cout « " " << o << " " << q << endl;

)

)

J

umożliwia rozwiązanie problemu połączeniowego. Podstawą algorytmu jest tablica liczb naturalnych o takiej własności, że/) i q są połączone wtedy i tylko wtedy, gdy p-ty element tablicy i ą-ty są równe. Elementy tablicy inicjujemy wartością i, gdzie 0 < i < n. Aby zaimplementować operację scalania elementów p i q, przeglądamy tablicę, zmieniając wszystkie elementy o tej samej nazwie co p tak, aby miały taką samą nazwę jak q. Wybór jest arbitralny - można równic dobrze zdecydować się na zmianę wszystkich elementów o tej samej nazwie co q na nazwę identyczną z p.

Rysunek 1.3 przedstawia zmiany w tablicy dla operacji scalania danych przykładowych z rysunku 1.1. Aby zrealizować funkcję wyszukiwania, musimy tylko sprawdzać, czy wskazane elementy tablicy są równe - stąd nazwa „szybkie wyszukiwanie”. Z kolei operacja scalania wymaga przeglądania całej tablicy dla każdej podanej na wejściu pary.

Twierdzenie 1.1. Rozwiązanie problemu połączeniowego za pomocą algorytmu szybkiego wyszukiwania wymaga wykonania co najmniej m n instrukcji, gdzie n oznacza liczbę obiektów, a m liczbę operacji scalania.

Dla każdej z m operacji scalania musimy przeprowadzić n iteracji pętli for. Każda iteracja wymaga przynajmniej jednej instrukcji (jeżeli tylko sprawdzamy, czy pętla powinna się zakończyć). ■

11