ScanImage007 (10)

*sm ;

1.2. PRZYKŁADOWY PROBLEM: POŁĄCZENIA    <>¹5; MH :    Mi

tość n - l, a negatywną - gdy jej nie osiągnie. Jest to inne pytanie spoza grupy pytań dotyczących połączeń, które chcemy zadać. Zbiór par wejściowych jest nazywany grafem, a zbiór par wynikowych drzewem rozpinającym tego grafit, minimalnym obiektem zapewniającym połączenia wszystkich obiektów (wierzchołków gTafli). Własności grafów, drzew rozpinających i całą grupę algorytmów związanych z tymi zagadnieniami poznamy w części 7¹.

Warto podjąć się zidentyfikowania podstawowych operacji, które będziemy wykonywać. Uczynimy w ten sposób dowolny algorytm związany z problemem analizy połączeń, który opracujemy, przydatnym dla całej palety podobnych problemów. Konkretnie, za każdym razem, kiedy otrzymujmy nową parę, najpierw musimy stwierdzić, czy tworzy ona nowe (nie znane dotąd) połączenie. Następnie musimy zawrzeć tę informację w strukturach danych, aby można było na jej podstawie w przyszłości sprawdzać kolejne pary. Przedstawimy te dwie czynności w postaci dwóch abstrakcyjnych operacji, traktując wejściowe liczby całkowite jako elementy abstrakcyjnych zbiorów, a następnie opracowując algorytmy i struktury danych, które mogą

•    odnaleźć zbiór zawierający dany element (operacja wyszukiwania),

•    zastąpić zbiory zawierające dwa dane elementy ich sumą (operacja sumowania zbiorów lub scalania).

Organizowanie naszych algorytmów' w kategoriach tych abstrakcyjnych operacji nie powoduje wyłączenia z naszych rozważań żadnych możliwości rozwiązania problemu połączeń, a operacje mogą się okazać przydatne również przy rozwiązywaniu innych problemów. Opracowywanie coraz bardziej uniwersalnych warstw abstrakcji jest immanentną cechą informatyki w ogóle, a analizy algorytmów w szczególności. Po metodę tę będziemy sięgać przy licznych okazjach w całej tej książce. W tym rozdziale abstrakcyjnym rozumowaniem posługujemy się w sposób nieformalny, chcemy bowdem jedynie posłużyć się nim jako metodą pisania programów rozwiązujących problem połączeń. Sposób translacji abstrakcji na kod C++ zostanie przedstawiony w rozdziale 4.

Problem połączeniowy można łatwo rozwiązać, jeżeli przedstawi się go w kategoriach abstrakcyjnych operacji wyszukiwania i scalania. Po przeczytaniu z wejścia now-ej pary p-q dla każdego elementu pary wykonuje się operację wyszukiwania. Jeżeli elementy pary znajdują się w tym samym zbiorze, wówczas pobieramy następną parę; jeżeli nie wykonujemy operację scalania i wypisujemy na wyjściu parę. Zbiory reprezentują składowe spójności: podzbiory obiektów' o takiej wdasności, że dowolne dwa zawarte w nich obiekty są połączone. Takie podejście skraca czas znalezienia rozwiązania algorytmicznego dla problemu połączeń i redukuje je do zdefiniowania struktur danych reprezentujących zbiory oraz napisania algorytmów dla operacji scalania i wyszukiwania, które w efektywny sposób w'ykorzystajązdefmiow'aną strukturę danych.

Istnieje wiele sposobów' reprezentacji i przetwarzania abstrakcyjnych zbiorów (zajmiemy się nimi szczegółowo w' rozdziale 4). W tym rozdziale skoncentrujemy się na stworzeniu reprezentacji, która zapewmi właściwą implementację dwóch operacji: scalania i wyszukiwania.

Zadania

1.1. Podaj wyniki, jakie powinien wygenerować algorytm analizy połączeń dla następujących par podanych na wejściu: 0-2, 1-4, 2-5, 3-6, 0-4,6-0 i 1-3.

1

Por. pizyp. 2 zc s. V.