Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00567 008490 10489544 na godz. na dobę w sumie
Algorytmy w C - książka
Algorytmy w C - książka
Autor: Liczba stron: 508
Wydawca: Helion Język publikacji: polski
ISBN: 83-7197-912-6 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> c - programowanie
Porównaj ceny (książka, ebook, audiobook).
Książka 'Algorytmy w C' jest doskonałą pomocą dla programistów, którym w codziennej pracy potrzebne są sprawdzone rozwiązania. Nie ma tu teoretycznych dywagacji tak charakterystycznych dla większości książek o strukturach danych i algorytmach. Znajdziesz w niej za to przystępnie podane informacje i praktyczne techniki programowania.

Wyjątkowo elegancki styl programowania i pisania autora, Kyle'a Loudona, ułatwia poznanie najważniejszych struktur danych, takich jak listy, stosy, kolejki, zbiory, sterty, kolejki priorytetowe i grafy. Autor prezentuje użycie algorytmów sortujących, wyszukiwania, analiz numerycznych, kompresji danych, szyfrowania danych, typowych algorytmów obsługi grafów oraz geometrii analitycznej. W rozdziałach poświęconych kompresji i szyfrowaniu czytelnik znajdzie nie tylko gotowy, szybki w działaniu kod, ale też informacje przydatne dla osób, które nigdy nie miały czasu ani chęci zagłębiać się w omawiane zagadnienia.

W tekście umieszczono także kody wraz z przykładami zastosowania poszczególnych struktur danych i algorytmów. Komplet kodów źródłowych znajduje się na płycie CD-ROM. Kod ten został napisany w taki sposób, byś łatwo mógł go wykorzystać we własnych aplikacjach.

W książce omówiono:

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI Algorytmy w C KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Autor: Kyle Loudon T³umaczenie: Tomasz ¯mijewski ISBN: 83-7197-912-6 Tytu³ orygina³u: Mastering Algorithms with C Format: B5, stron: 492 Przyk³ady na ftp: 272 kB Ksi¹¿ka „Algorytmy w C” jest doskona³¹ pomoc¹ dla programistów, którym w codziennej pracy potrzebne s¹ sprawdzone rozwi¹zania. Nie ma tu teoretycznych dywagacji tak charakterystycznych dla wiêkszoġci ksi¹¿ek o strukturach danych i algorytmach. Znajdziesz w niej za to przystêpnie podane informacje i praktyczne techniki programowania. Wyj¹tkowo elegancki styl programowania i pisania autora, Kyle’a Loudona, u³atwia poznanie najwa¿niejszych struktur danych, takich jak listy, stosy, kolejki, zbiory, sterty, kolejki priorytetowe i grafy. Autor prezentuje u¿ycie algorytmów sortuj¹cych, wyszukiwania, analiz numerycznych, kompresji danych, szyfrowania danych, typowych algorytmów obs³ugi grafów oraz geometrii analitycznej. W rozdzia³ach poġwiêconych kompresji i szyfrowaniu czytelnik znajdzie nie tylko gotowy, szybki w dzia³aniu kod, ale te¿ informacje przydatne dla osób, które nigdy nie mia³y czasu ani chêci zag³êbiaæ siê w omawiane zagadnienia. W tekġcie umieszczono tak¿e kody wraz z przyk³adami zastosowania poszczególnych struktur danych i algorytmów. Komplet kodów ĥród³owych znajduje siê na p³ycie CD-ROM. Kod ten zosta³ napisany w taki sposób, byġ ³atwo móg³ go wykorzystaæ we w³asnych aplikacjach. W ksi¹¿ce omówiono: • Wskaĥniki • Rekurencjê • Analizê algorytmów • Struktury danych (listy, stosy, kolejki, zbiory, tablice asocjacyjne, drzewa, sterty, kolejki priorytetowe i grafy) • Sortowanie i wyszukiwanie • Metody numeryczne • Kompresjê danych • Szyfrowanie danych • Algorytmy operuj¹ce na grafach Spis treści Wstęp .....................................................................................................................z..................... 9 Część I Zagadnienia podstawowe...................................................g..................... 15 Rozdział 1. Wprowadzenie ....................................................................................z...................17 Wprowadzenie do struktur danych ...................................................n............................................ 18 Wprowadzenie do algorytmów ...................................................n................................................... 19 Odrobina inżynierii oprogramowania ...................................................n........................................ 22 Jak tej książki używać ...................................................n...................................................n... .............. 23 Rozdział 2. Użycie wskaźników ............................................................................z................... 25 Podstawowe informacje o wskaźnikach ...................................................n..................................... 26 ................. 27 Alokacja pamięci...................................................n...................................................n......... Agregaty i arytmetyka wskaźników ...................................................n........................................... 29 Wskaźniki jako parametry funkcji ...................................................n............................................... 31 Wskaźniki ogólne i rzutowanie...................................................n.................................................... 34 Wskaźniki do funkcji ...................................................n...................................................n..... ............. 37 ............. 38 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... .............. 39 Rozdział 3. Rekurencja ..........................................................................................z................... 41 .............. 42 ........ 46 ............. 48 .............. 50 Podstawy rekurencji...................................................n...................................................n...... Rekurencja prawostronna ...................................................n...................................................n.. Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... Rozdział 4. Analiza algorytmów ...........................................................................z................... 51 Analiza najgorszego przypadku ...................................................n.................................................. 52 ....................... 53 O-notacja ...................................................n...................................................n................ Złożoność obliczeniowa ...................................................n...................................................n... .......... 55 4 Algorytmy w C Przykład analizy: sortowanie przez wstawianie ...................................................n....................... 57 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............. 59 .............. 60 Część II Struktury danych ...................................................g............................... 61 Rozdział 5. Listy powiązane...................................................................................z.................. 63 Opis list powiązanych..............................n...................................................n......................... ............. 64 Interfejs list powiązanych...................................................n.............................................................. 65 Implementacja list powiązanych i analiza kodu ...................................................n....................... 68 Przykład użycia list powiązanych: zarządzanie ramkami ...................................................n...... 75 Opis list podwójnie powiązanych ...................................................n............................................... 78 Interfejs list podwójnie powiązanych...................................................n.......................................... 79 Implementacja list podwójnie powiązanych i analiza kodu ...................................................n... 81 Opis list cyklicznych ...................................................n...................................................n.... ............... 90 Interfejs list cyklicznych ...................................................n................................................................ 91 Implementacja list cyklicznych i analiza kodu ...................................................n.......................... 93 Przykład użycia list cyklicznych: zamiana stron...................................................n....................... 98 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ........... 101 ............ 103 Rozdział 6. Stosy i kolejki .....................................................................................z................. 105 .................. 106 Opis stosów ...................................................n...................................................n.............. Interfejs stosu ...................................................n...................................................n.......... ................... 107 Implementacja stosu i analiza kodu ...................................................n..........................................108 ................... 111 Opis kolejek ...................................................n...................................................n............. Interfejs kolejek ...................................................n...................................................n........ .................. 111 Implementacja kolejki i analiza kodu...................................................n........................................113 Przykład użycia kolejek: obsługa zdarzeń ...................................................n............................... 116 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ........... 118 ............ 119 Rozdział 7. Zbiory .................................................................................................z................. 121 ................. 122 Opis zbiorów ...................................................n...................................................n............. Interfejs zbiorów ...................................................n...................................................n........ ................ 124 Implementacja zbioru i analiza kodu ...................................................n........................................ 127 Przykład użycia zbiorów: pokrycie ...................................................n...........................................137 ........... 141 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 143 Rozdział 8. Tablice asocjacyjne .............................................................................z................. 145 Opis łańcuchowych tablic asocjacyjnych ...................................................n.................................. 147 Interfejs łańcuchowych tablic asocjacyjnych ...................................................n............................ 150 Implementacja łańcuchowej tablicy asocjacyjnej i analiza kodu.............................................. 152 Przykład użycia łańcuchowych tablic asocjacyjnych: tablice symboli.................................... 159 Tablice asocjacyjne z otwartym adresowaniem...................................................n....................... 162 Interfejs tablic asocjacyjnych z otwartym adresowaniem ...................................................n...... 166 Spis treści 5 Implementacja tablicy asocjacyjnej z otwartym adresowaniem i analiza kodu .................... 167 ........... 175 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 177 Rozdział 9. Drzewa ...............................................................................................z................. 179 ............... 181 Drzewa binarne...................................................n...................................................n........... Interfejs drzew binarnych ...................................................n...................................................n........ 184 Implementacja drzew binarnych i analiza kodu ...................................................n..................... 187 Przykład użycia drzewa binarnego: przetwarzanie wyrażeń.................................................. 198 Binarne drzewa wyszukiwania ...................................................n.................................................. 201 Interfejs binarnych drzew wyszukiwania ...................................................n................................ 203 Implementacja binarnych drzew wyszukiwania i analiza kodu ............................................. 205 ........... 227 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 228 Rozdział 10. Sterty i kolejki priorytetowe.............................................................z................. 231 ......................... 232 Sterty...................................................n...................................................n................... Interfejs stert ...................................................n...................................................n.......... ..................... 233 Implementacja stert i analiza kodu...................................................n............................................ 235 Kolejki priorytetowe ...................................................n...................................................n..... ............ 245 Interfejs kolejek priorytetowych...................................................n................................................. 245 Implementacja kolejek priorytetowych i analiza kodu ...................................................n.......... 247 Przykład zastosowania kolejek priorytetowych: sortowanie paczek...................................... 248 ........... 250 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 251 Rozdział 11. Grafy.................................................................................................z................. 253 ........................ 254 Grafy ...................................................n...................................................n.................... Interfejs grafów ...................................................n...................................................n......... ................. 260 Implementacja grafów i analiza kodu...................................................n....................................... 264 Przykład użycia grafów: zliczanie kroków w ruchu po sieci...................................................n 275 Przykład użycia grafów: sortowanie topologiczne ...................................................n................. 281 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ........... 285 ............ 287 Część III Algorytmy ...................................................g....................................... 289 Rozdział 12. Sortowanie i przeszukiwanie ...........................................................z................. 291 Sortowanie przez wstawianie...................................................n..................................................... 293 Interfejs sortowania przez wstawianie...................................................n...................................... 293 Implementacja sortowania przez wstawianie i analiza kodu .................................................. 294 ..................... 296 Quicksort...................................................n...................................................n................ Interfejs quicksort ...................................................n...................................................n...... ................ 297 Implementacja quicksort i analiza kodu ...................................................n................................... 298 Przykład użycia quicksort: zawartość katalogu ...................................................n...................... 303 Sortowanie przez złączanie...................................................n......................................................... 306 Interfejs sortowania przez złączanie ...................................................n......................................... 307 Implementacja sortowania przez złączanie i analiza kodu ...................................................n... 307 6 Algorytmy w C ........ 312 Sortowanie ze zliczaniem ...................................................n...................................................n. Interfejs sortowania ze zliczaniem...................................................n............................................. 313 Implementacja sortowania ze zliczaniem i analiza kodu...................................................n....... 313 Sortowanie na bazie ...................................................n...................................................n...... ............ 317 Interfejs sortowania na bazie ...................................................n...................................................... 317 Implementacja sortowania na bazie i analiza kodu...................................................n................ 318 Wyszukiwanie binarne ...................................................n...................................................n..... ........ 321 Interfejs wyszukiwania binarnego...................................................n............................................. 321 Implementacja wyszukiwania binarnego i analiza kodu...................................................n....... 322 Przykład użycia przeszukiwania binarnego: kontrola pisowni............................................... 324 ........... 326 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 328 Rozdział 13. Metody numeryczne.........................................................................z................. 329 Przybliżanie wielomianami ...................................................n...................................................n..... 330 Interfejs interpolacji wielomianowej...................................................n.......................................... 334 Implementacja interpolacji wielomianowej i analiza kodu ...................................................n... 334 Oszacowanie najmniejszymi kwadratami ...................................................n................................ 337 Interfejs oszacowania najmniejszymi kwadratami...................................................n.................. 339 Implementacja szacowania najmniejszymi kwadratami i analiza kodu ................................ 339 Rozwiązywanie równań ...................................................n...................................................n..... ...... 340 Interfejs rozwiązywania równań...................................................n................................................ 345 Implementacja rozwiązywania równań i analiza kodu ...................................................n......... 345 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ........... 347 ............ 348 Rozdział 14. Kompresja danych ............................................................................z................. 349 Operatory bitowe...................................................n...................................................n......... .............. 352 Interfejs operacji bitowych ...................................................n.......................................................... 353 Implementacja operacji bitowych i analiza kodu ...................................................n.................... 354 ....... 358 Kodowanie Huffmana ...................................................n...................................................n....... Interfejs kodowania Huffmana ...................................................n.................................................. 362 Implementacja kodowania Huffmana i analiza kodu ...................................................n............ 362 Przykład użycia kodowania Huffmana: optymalizacja przesyłania przez sieć .................... 376 Algorytm LZ77...................................................n...................................................n............ ............... 378 Interfejs LZ77...................................................n...................................................n........... ................... 382 Implementacja LZ77 i analiza kodu ...................................................n.......................................... 382 ........... 395 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 397 Rozdział 15. Szyfrowanie danych .........................................................................z................. 399 ......................... 402 DES...................................................n...................................................n...................... Interfejs DES ...................................................n...................................................n............ ................... 409 Implementacja DES i analiza kodu...................................................n............................................410 Przykład użycia DES: blokowe tryby szyfrowania...................................................n................. 420 Algorytm RSA...................................................n...................................................n............. Interfejs RSA...................................................n...................................................n............ ............... 423 ................... 426 Spis treści 7 Implementacja RSA i analiza kodu...................................................n............................................427 ........... 430 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 432 Rozdział 16. Algorytmy operujące na grafach......................................................z................. 435 ........... 438 Drzewa minimalne ...................................................n...................................................n......... Interfejs drzew minimalnych...................................................n...................................................... 439 Implementacja i analiza kodu...................................................n..................................................... 441 Najkrótsze ścieżki ...................................................n...................................................n....... ............... 446 Interfejs najkrótszych ścieżek ...................................................n..................................................... 447 Implementacja najkrótszej ścieżki i analiza kodu ...................................................n................... 449 Przykład użycia najkrótszych ścieżek: tablic tras...................................................n.................... 454 Problem komiwojażera ...................................................n...................................................n..... ........ 457 Interfejs problemu komiwojażera ...................................................n.............................................. 459 Implementacja problemu komiwojażera i analiza kodu ...................................................n........ 460 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ........... 464 ............ 465 Rozdział 17. Algorytmy geometryczne .................................................................z................. 467 Sprawdzanie, czy odcinki się przecinają ...................................................n.................................. 470 Interfejs sprawdzania, czy odcinki się przecinają ...................................................n................... 473 Implementacja sprawdzenia, czy odcinki się przecinają i analiza kodu ................................ 473 Obrys wypukły ...................................................n...................................................n............ .............. 475 Interfejs obrysów wypukłych ...................................................n..................................................... 477 Implementacja obrysu wypukłego i analiza kodu ...................................................n.................. 478 Długość łuku na powierzchniach sferycznych ...................................................n........................ 482 Interfejs długości łuku na powierzchniach sferycznych ...................................................n........ 485 Implementacja długości łuku na powierzchniach sferycznych i analiza kodu ..................... 485 Przykład użycia długości łuku: przybliżone określanie odległości na Ziemi ....................... 486 ........... 489 Pytania i odpowiedzi ...................................................n...................................................n..... Tematy pokrewne...................................................n...................................................n.......... ............ 492 Skorowidz................................................................................................................z................ 493 Algorytmy operujące na grafach Grafy to elastyczne struktury danych pozwalające modelować problemy jako relacje czy powiązania między obiektami (więcej na ten temat w rozdziale 11.). W tym rozdziale przedstawimy algorytmy operujące na grafach. Jak zobaczymy, wiele z tych algorytmów przypomina podstawowe algorytmy przeszukiwania grafów wszerz i w głąb, opisane w rozdziale 11. Te dwie grupy algorytmów są ważne dla innych algorytmów operujących na grafach, jako że pozwalają systematycznie przeglądalć graf. Istotna różnica między algorytmami z tego rozdziału i rozdziału 11. polega na tym, że algo- rytmy tego rozdziału dotyczą grafów z wagami. W takich grafach każdej krawędzi przypisuje się pewną wartość, wagę, która wizualnie jest zaznaczana jako niewielka liczba przy kra- wędzi. Wprawdzie wagi mogą oznaczać różne rzeczy, ale zwykle opisują koszt związany z przejściem danej krawędzi. Grafy z wagami i działające na nich algorytmy pozwalają opi- sywać ogromną liczbę różnorodnych problemów. Listing 16.1 to nagłówek do algorytmów operujących na grafach, zaprezentowanych w tym rozdzliale. Listing 16.1. Plik nagłówkowy algorytmów operującyc.h na grafach /**************************************************l*************************** * l * * ------------------------------ graphalg.h ------l------------------------ * * l * ***************************************************l**************************/ #ifndef GRAPHALG_H #define GRAPHALG_H #include graph.h #include list.h 436 Rozdział 16. Algorytmy operujące na grafach /**************************************************l*************************** * l * * Struktura na węzły drzew minimalnych. l * * l * ***************************************************l**************************/ typedef struct MstVertex_ { void *data; double weight; VertexColor color; double key; struct MstVertex_ *parent; } MstVertex; /**************************************************l*************************** * l * * Struktura na węzły najkrótszej ścieżki. l * * l * ***************************************************l**************************/ typedef struct PathVertex_ { void *data; double weight; VertexColor color; double d; struct PathVertex_ *parent; } PathVertex; /**************************************************l*************************** * l * * Struktura na węzły problemu komiwojażera. l * * l * ***************************************************l**************************/ typedef struct TspVertex_ { void *data; double x, y; VertexColor color; } TspVertex; /**************************************************l*************************** * l * * --------------------------- Interfejs publiczny ---l--------------------- * * l * ***************************************************l**************************/ int mst(Graph *graph, const MstVertex *start, List *spanl, int (*match)(const void *key1, const void *key2)); Drzewa minimalne 437 int shortest(Graph *graph, const PathVertex *start, Listl *paths, int (*match) (const void *key1, const void *key2)); int tsp(List *vertices, const TspVertex *start, List *toulr, int (*match) (const void *key1, const void *key2)); #endif W tym rozdziale omówimy: Drzewa minimalne Drzewa będące abstrakcjami wielu problemów związanych z połączeniami. Drzewo minimalne to takie drzewo, które łączy wszystkie węzły w nieskierowanym grafie z wagami możliwie najmniejszym kosztem. Najkrótsze ścieżki Wynik rozwiązywania różnego rodzaju problemów najkrótszej drogi. Najkrótsza droga lub ścieżka to droga w grafie skierowanym z wagami dwa węzły przy minimalnym koszcie. Problem komiwojażera Zaskakująco trudny problem, w którym szukamy najkrótszej drogi pozwalającej odwie- dzić wszystkie węzły zupełnego, nieskierowanego grafu z wagami tak, aby przed po- wrotem do punktu startowego każdy węzeł został odwiedzony dokładnie raz. Oto wybrane zastosowania algorytmów operujących na gralfach: Dobrze dobrane sieci przesyłowe Praktyczne zagadnienie dotyczące przesyłania wody, ropy i innych cieczy. Jeśli punkty odbioru medium z sieci zostaną przedstawione jako węzły grafu, zaś potencjalne połą- czenia jako krawędzie tego grafu z wagami odpowiadającymi kosztowi połączenia punk- tów, drzewo minimalne wskazuje optymalny przebieg sieci łączącej wszystkie punkty odbioru. Tablice tras (przykład w rozdziale) Tablice używane przez rutery do przesyłania danych w Internecie. Zadaniem rutera jest przesłanie danych bliżej ich miejsca docelowego. W przypadku jednego ze sposobów wyznaczania tras rutery okresowo wyliczają najkrótsze ścieżki między sobą, dzięki czemu każdy z nich potrafi wykonać następny etap prlzesłania danych. Usługi dostawcze Usługi związane zwykle z odwiedzaniem licznych miejsc w celu odbierania i dostar- czania paczek. Rozwiązanie problemu komiwojażera pozwala wskazać najlepszą drogę kuriera, który przed powrotem do bazy musi odwiedzićl wszystkie punkty. Sieci komunikacyjne Sieci zawierające wiele różnego rodzaju sprzętu: linie telefoniczne, stacje przekaźnikowe i systemy satelitarne. Wszystkie te urządzenia muszą zostać optymalnie rozmieszczone. Optymalny rozkład można obliczyć przez wyznaczenie drzewa minimalnego grafu z wagami opisującego sieć. 438 Rozdział 16. Algorytmy operujące na grafach Kierowanie samolotów Problem optymalizacyjny szczególnie istotny w liniach lotniczych i agencjach kontroli lotu. Samoloty często nie mogą przemieszczać się bezpośrednio między wyznaczonymi punktami, gdyż muszą korzystać z korytarzy powietrznych (takich lotniczych autostrad), poza tym obowiązują ograniczenia nałożone przez kontrolerów lotów. Optymalna droga między dwoma punktami to ścieżka z najmniejszymi wagalmi. System transportu zamkniętego Systemy, w których pojazdy szynowe lub wózki wielokrotnie poruszają się między tymi samymi punktami. Takie systemy mogą być użyte do rozwożenia części w fabryce lub do przenoszenia towarów w magazynie. Rozwiązanie problemu komiwojażera pozwala znaleźć optymalny układ systemu. Mostkowanie obwodów elektrycznych Problem optymalizacyjny związany z produkcją elektroniki. Często trzeba połączyć ze sobą punkty obwodu przy użyciu grafu, w którym poszczególnym punktom odpowia- dają węzły. Potencjalne połączenia modelowane są jako krawędzie. Rozwiązanie opty- malne znowu wskazuje drzewo minimalne. Monitorowanie ruchu kołowego Obserwowanie zmian ruchu zmierzające do wyznaczenia najlepszej trasy poruszania się po mieście. Aby uniknąć nadmiernych opóźnień związanych z korkami, używa się modelu zawierającego informacje o połączeniach i bada się przecięcia z najmniejszym ruchem. Drzewa minimalne Wyobraźmy sobie pinezki powbijane w tablicę i połączone sznurkiem. Przy założeniu, że wędrując po sznurku możemy dotrzeć do wszystkich pinezek, wyobraźmy sobie grę, której celem jest usuwanie sznurków dotąd, aż pinezki będą połączone najmniejszą możliwą liczbą sznurków. To jest właśnie idea drzew minimalnych. Formalnie, jeśli mamy nieskierowany graf z wagami G = (V, E), jego drzewem minimalnym jest zbiór T krawędzi ze zbioru E łączący wszystkie węzły z V przy możliwie najmniejszym koszcie. Krawędzie z T tworzą drzewo, gdyż każdy węzeł ma dokładnie jednego rodzica — węzeł poprzedni, z wyjątkiem węzła początkowego, który jest korzeniem drzewa. Algorytm Prima Jedną z metod wyznaczania drzew minimalnych jest algorytm Prima. Algorytm ten rozpina drzewo minimalne dodając kolejno krawędzie według ich chwilowej wartości, zatem zali- czamy go do grupy algorytmów zachłannych (rozdział 1.). Wprawdzie algorytmy zachłanne często zamiast najlepszych rozwiązań dają jedynie ich przybliżenia, jednak algorytm Prima daje faktycznie rozwiązanie optymalne. Interfejs drzew minimalnych 439 Algorytm ten działa poprzez wielokrotne wybieranie węzła i badanie jego krawędzi przy- legających w celu sprawdzenia, czy istnieje szybsza droga połączenia zbadanych dotąd węzłów. Algorytm ten przypomina przeszukiwanie wszerz, gdyż badane są wszystkie krawędzie sąsiednie węzła i dopiero wtedy robione jest przejście głębiej w strukturę grafu. Wartość kluczowa węzła, od którego zaczynamy szukanie to 0. Aby wybrać odpowiedni węzeł na każdym etapie działania algorytmu, zapamiętujemy kolor i wartość klucza dla każdego węzła. Początkowo wszystkie węzły są białe, wszystkie wartości kluczy mają wartość ∞: dowol- nie dużą liczbę, większą od wag wszystkich krawędzi wl grafie. Ustawiamy wartość klucza węzła, od którego zaczynamy na 0. W miarę działania algorlytmu przypisujemy wszystkim węzłom poza węzłem początkowym rodzica w drzewie minimalnym. Węzeł jest częścią drzewa minimalnego tylko wtedy, gdy stanie się czarny; przed tym jego rodzic może się zmieniać. Dalej algorytm Prima działa następująco: najpierw, spośród wszystkich białych węzłów grafu wybieramy jeden węzeł u, który ma najmniejszą wartość klucza. Początkowo będzie to węzeł startowy, gdyż ma wartość 0. Po wybraniu węzła malujemy go na czarno. Następ- nie, dla każdego białego węzła v przylegającego do u, jeśli waga krawędzi (u,v) jest mniejsza od wartości klucza v, ustawiamy wartość klucza v na wagę (u, v) i ustalamy u jako rodzica v. Proces powtarzamy dotąd, aż zaczernione zostaną wszystkie węzły. W miarę wzrostu drzewa minimalnego wchodzą do niego wszystkie krawędzie mające na dowolnym końcu czarne węzły. Na rysunku 16.1 pokazano wyliczanie drzewa minimalnego za pomocą algorytmu Prima. Wartości klucza i rodzic pokazywane są obok węzła. Wartość klucza jest na lewo od uko- śnika, rodzic na prawo. Wyszarzone krawędzie to krawędzie rosnącego drzewa minimal- nego. Drzewo minimalne przedstawione na rysunku ma łączną wagę 17. Interfejs drzew minimalnych mst int mst(Graph *graph, const MstVertex *start, List *span, int (*match) (const void *key1, const void *key2)); Zwracana wartość: 0, jeśli wyznaczanie drzewa minimalnego się powiodło, i –1 w przeciw- nym razie. Opis: Wyliczane jest drzewo minimalne nieskierowanego grafu z wagami graph. Operacja modyfikuje graf, więc w razie potrzeby trzeba zrobić jego kopię. Każdy węzeł grafu graph musi zawierać dane typu MstVertext. Każdej krawędzi przypisujemy wagę, ustawiając pole weight struktury MstVertext na wartość przekazaną jako data2 do graph_ins_edge. Korzystając z pola data poszczególnych struktur MstVertext, zapisujemy dane tego wę- zła, na przykład jego identyfikator. Funkcja match grafu ustawiana przy inicjalizacji grafu za pomocą graph_init służy do porównywania jedynie pól data struktur MstVertext. Jest 440 Rozdział 16. Algorytmy operujące na grafach Rysunek 16.1. Wyliczanie minimalnego drzewa za pomocą .algorytmu Prima to ta sama funkcja, która przekazywana jest do mst jako match. Po realizacji algorytmu uzy- skane drzewo minimalne jest przekazywane jako span; węzeł, którego rodzic to NULL, jest korzeniem całego drzewa. Elementy parent pozostałych pól wskazują węzły poprzedzające dany węzeł w drzewie. Węzły ze span wskazują faktycznie węzły z grafu graph, więc trzeba zapewnić istnienie odpowiednich danych tak dlługo, jak długo będą potrzebne. Złożoność: O(EV2), gdzie V jest liczbą węzłów grafu, a E — liczbą jego krawędzi. Jednak po niewielkiej, przedstawionej dalej poprawce, algorytm działa w czasie O(E lg V) (zobacz tematy powiązane na końcu tego rozdziału). Implementacja i analiza kodu 441 Implementacja i analiza kodu Aby wyznaczyć drzewo minimalne nieskierowanego grafu z wagami, najpierw trzeba zapisać graf z wagami w abstrakcyjnym typie danych przedstawionym w rozdziale 11. Konieczne będzie też pamiętanie informacji potrzebnych w algorytmie Prima, związa- nych z węzłami i krawędziami. Do tego służy struktura MstVertext; używamy jej na węzły grafu, które mają być włączane do drzewa minimalnego (listing 16.2). Struktura ta ma pięć elementów: data to dane związane z węzłem, weight to waga krawędzi przylegającej do węzła, color to kolor węzła, a key to wartość klucza węzła, zaś parent to rodzic węzła w drzewie minimalnym. Listing 16.2. Implementacja wyliczania drzewa minimaln.ego /**************************************************l*************************** * l * * --------------------------------- mst.c --------l------------------------ * * l * ***************************************************l**************************/ #include float.h #include stdlib.h #include graph.h #include graphalg.h #include list.h /**************************************************l*************************** * l * * ---------------------------------- mst ---------l------------------------ * * l * ***************************************************l**************************/ int mst(Graph *graph, const MstVertex *start, List *spanl, int (*match)(const void *key1, const void *key2)) { AdjList *adjlist; MstVertex *mst_vertex, *adj_vertex; ListElmt *element, *member; double minimum; int found, i; /**************************************************l*************************** * l * * Inicjalizacja wszystkich węzłów grafu. l * * l * ***************************************************l**************************/ found = 0; for (element = list_head( graph_adjlists(graph)); element != lNULL; element = list_next(element)) { 442 Rozdział 16. Algorytmy operujące na grafach mst_vertex = ((AdjList *)list_data(element))- vertex; if (match(mst_vertex, start)) { /********************************************l*************************** * l * * Inicjalizacja węzła początkowego. l * * l * *********************************************l**************************/ mst_vertex- color = white; mst_vertex- key = 0; mst_vertex- parent = NULL; found = 1; } else { /********************************************l*************************** * l * * Inicjalizacja węzłów poza węzłem początkowym. l * * l * *********************************************l**************************/ mst_vertex- color = white; mst_vertex- key = DBL_MAX; mst_vertex- parent = NULL; } } /**************************************************l*************************** * l * * Jeśli nie znaleziono węzła początkowego, kończymy. l * * l * ***************************************************l**************************/ if (!found) return -1; /**************************************************l*************************** * l * * Wyznaczamy drzewo minimalne algorytmem Prima. l * * l * ***************************************************l**************************/ i = 0; while (i graph_vcount(graph)) { /***********************************************l*************************** * l * * Wybieramy biały węzeł o najmniejszej wartości klucza. l * * l * ************************************************l**************************/ minimum = DBL_MAX; for (element = list_head( graph_adjlists(graph)); elementl != NULL; element = list_next(element)) { Implementacja i analiza kodu 443 mst_vertex = ((AdjList *)list_data(element))- vertex; if (mst_vertex- color == white mst_vertex- key minimum) l{ minimum = mst_vertex- key; adjlist = list_data(element); } } /***********************************************l*************************** * l * * Zaczerniamy wybrany węzeł. l * * l * ************************************************l**************************/ ((MstVertex *)adjlist- vertex)- color = black; /***********************************************l*************************** * l * * Przeglądamy wszystkie węzły sąsiadujące z węzłem wybranym. l * * l * ************************************************l**************************/ for (member = list_head( adjlist- adjacent); member != NULL; membelr = list_next(member)) { adj_vertex = list_data(member); /********************************************l*************************** * l * * Znalezienie węzła sąsiadującego z listy struktur sąlsiedztwa. * * l * *********************************************l**************************/ for (element = list_head( graph_adjlists(graph)); elelment != NULL; element = list_next(element)) { mst_vertex = ((AdjList *)list_data(element))- vertexl; if (match(mst_vertex, adj_vertex)) { /**************************************l*************************** * l * * Decydujemy, czy zmieniamy wartość klucza i rodzical węzła * * sąsiedniego z listy struktur list sąsieldztwa. * * l * ***************************************l**************************/ if (mst_vertex- color == white adj_vertex- weighlt mst_vertex- key) { mst_vertex- key = adj_vertex- weight; mst_vertex- parent = adjlist- vertex; } break; } } 444 } Rozdział 16. Algorytmy operujące na grafach /***********************************************l*************************** * l * * Przygotowujemy się do wyboru następnego węzła. l * * l * ************************************************l**************************/ i++; } /**************************************************l*************************** * l * * Ładujemy drzewo minimalne na listę. l * * l * ***************************************************l**************************/ list_init(span, NULL); for (element = list_head( graph_adjlists(graph)); element != lNULL; element = list_next(element)) { /***********************************************l*************************** * l * * Ładowanie wszystkich czarnych węzłów z listy sąsiedztwa. l * * l * ************************************************l**************************/ mst_vertex = ((AdjList *)list_data(element))- vertex; if (mst_vertex- color == black) { if (list_ins_next(span, list_tail(span), mst_vertex)l != 0) { list_destroy(span); return -1; } } } return 0; } Budowa grafu ze struktur MstVertex wygląda niemalże tak samo, jak budowa grafu za- wierającego inne typy danych. Do wstawienia węzła do grafu używamy graph_ins_vertex i przekazujemy jako dane data strukturę MstVertex. Analogicznie, aby wstawić krawędź, wywołujemy graph_ins_edge, i jako data1 i data2 przekazujemy struktury data1 i data2. Podczas wstawiania węzła ustawiamy jedynie pole data struktury MstVertex. Przy wstawianiu krawędzi ustawiamy pole data struktury data1 oraz pola data i weight struktury data2. Występujące w data2 pole weight jest wagą krawędzi od węzła opisy- wanego przez data1 do węzła opisywanego przez data2. Praktycznie wagi wylicza się i zapisuje zwykle jako liczby zmiennoprzecinkowe. Wartości kluczy wylicza się na pod- stawie wag, więc też są to liczby zmiennoprzecinkowe. Implementacja i analiza kodu 445 Operacja mst najpierw inicjalizuje wszystkie węzły z listy sąsiedztwa. Początkowe wartości kluczy wszystkich węzłów ustawiamy na DBL_MAX, jedynie węzeł początkowy otrzymuje wartość 0.0. Przypomnijmy, że w typie abstrakcyjnym grafów graf jest listą struktur sąsiedz- twa, struktura odpowiadająca każdemu węzłowi zawiera ten właśnie węzeł oraz zbiór węzłów doń przylegających (więcej na ten temat w rozdziale 11.). Dla węzła zapisanego w strukturze listy sąsiedztwa zapisujemy jego kolor, wartość klucza i rodzica. Aby wszystkie te informacje zgromadzić w jednym miejscu, korzystamy z samego węzła, a nie z węzłów z jego listy sąsiedztwa. Ten sam węzeł może się pojawić na wielu listach sąsiedztwa, ale każdy węzeł wraz ze swoją listą występuje dokładnie rlaz. Najważniejszym punktem algorytmu Prima jest pojedyncza pętla realizująca iterację raz dla każdego węzła grafu. Każdą iterację zaczynamy od wybrania węzła mającego najmniejszą wartość klucza pośród białych węzłów. Zaczerniamy ten węzeł, następnie przechodzimy po węzłach z nim sąsiadujących. Podczas ich przeglądania sprawdzamy kolor i wartość klu- cza, porównujemy je z kolorem i wartością klucza wybranego węzła. Jeśli węzeł sąsiedni jest biały, a jego klucz ma wartość mniejszą od klucza wybranego węzła, ustawiamy wartość klucza sąsiedniego węzła na wagę krawędzi między węzłem wybranym i sąsiednim, poza tym jako rodzica węzła sąsiedniego ustalamy węzeł bieżący. Aktualizujemy odpowiednie informacje dla węzła sąsiedniego. Cały proces powtarzalmy, aż wszystkie węzły będą czarne. Kiedy kończy się pętla główna algorytmu Prima, wyliczanie drzewa minimalnego jest skoń- czone. W tej chwili wszystkie czarne struktury MstVertex z list sąsiedztwa wstawiamy na listę powiązaną span. Znajdujący się na tej liście węzeł mający rodzica o wartości NULL jest korzeniem drzewa. Element parent wszystkich innych węzłów wskazuje węzeł poprzedzający go w drzewie. Pole weight poszczególnych struktur MstVertex nie jest wypełniane, gdyż jest ono potrzebne jedynie do zapisywania wag na listach sąsiedztwa. Na rysunku 16.2 pokazano takie struktury MstVertex, jakie zostaną zwrócone po wyzna- czeniu drzewa minimalnego grafu z rysunku 16.1. Rysunek 16.2. Lista zwracana przez funkcję mst jako drze.wo minimalne grafu z rysunku 16.1 Złożoność mst wynosi O(EV2), gdzie V jest liczbą węzłów grafu, zaś E jest liczbą krawędzi. Wynika to ze sposobu działania pętli głównej, w której wybieramy węzły i porównujemy wagi i wartości kluczy. Dla każdego spośród V węzłów najpierw przeglądamy V elemen- tów z list sąsiedztwa w celu sprawdzenia, który biały węzeł ma najmniejszą wartość klu- cza. Ta część pętli ma zatem złożoność O(V2). Następnie dla każdego węzła sąsiadującego z wybranym węzłem sprawdzamy listę sąsiedztwa, aby sprawdzić, czy trzeba zmienić 446 Rozdział 16. Algorytmy operujące na grafach wartość klucza i zmienić rodzica. Dla wszystkich V węzłów E razy sprawdzamy listę — raz dla każdej krawędzi. Każde z tych sprawdzeń wymaga czasu O(V), jest to czas przeszuki- wania listy. Wobec tego dla wszystkich wybieranych V węzłów operacja o złożoności O(V) wykonywana jest E razy. W związku z tym ta część pętli ma złożoność O(EV2), a całkowita złożoność pętli głównej wynosi O(V2 + EV2), czyli O(EV2). Pętle przed pętlą główną i za nią mają złożoność O(V), więc złożoność mst wynosi O(EV2). Przypomnijmy jednak, że niewiel- kim nakładem pracy można poprawić szybkość działania algorytmu Prima do O(E lg V) (pokażemy to pod koniec rozdziału). Najkrótsze ścieżki Znalezienie najkrótszej ścieżki lub ścieżki o najmniejszej wadze między wskazanymi węzłami grafu jest istotą wielu problemów związanych ze znajdowaniem drogi. Formalnie, jeśli mamy skierowany graf z wagami G = (V, E), najkrótsza ścieżka z węzła s do węzła t ze zbioru V jest zbiorem S krawędzi z E takim, że s łączy t po minimalnym koszcie. Znajdując S rozwiązujemy problem najkrótszej ścieżki między pojedynczą parą węzłów. W tym celu tak naprawdę rozwiązujemy ogólniejszy problem najkrótszej ścieżki z pojedynczego źró- dła, problem pojedynczej pary rozwiązując niejako „przy okazji”. W przypadku problemu z pojedynczym źródłem, wyznaczamy najkrótsze ścieżki z węzła początkowego s do wszyst- kich pozostałych węzłów z niego osiągalnych. Robimy tak dlatego, że nie jest znany żaden algorytm, który szybciej rozwiązywałby problem z pojedlynczą parą węzłów. Algorytm Dijkstry Jednym z rozwiązań problemu najkrótszej ścieżki z pojedynczego źródła jest algorytm Dijkstry. Algorytm ten pozwala budować drzewo najkrótszych ścieżek, którego korzeniem jest węzeł początkowy s, a gałęziami są najkrótsze ścieżki z s do wszystkich węzłów z G. Algo- rytm ten wymaga, aby wagi krawędzi były nieujemne. Podobnie jak w przypadku algo- rytmu Prima, algorytm Dijkstry należy do grupy algorytmów zachłannych, które akurat dają optymalne rozwiązanie. Algorytm ten jest algorytmem zlachłannym, gdyż nowe krawędzie dodawane są do drzewa najkrótszej ścieżki według ich olceny w danej chwili. Podstawą algorytmu Dijkstry jest wielokrotne wybieranie węzłów i badanie krawędzi przylegających do nich w celu określenia, czy najkrótsza ścieżka do poszczególnych węzłów może zostać poprawiona. Algorytm ten jest nieco podobny do przeszukiwania wszerz, gdyż najpierw badane są wszystkie krawędzie przylegające do węzła, dopiero potem przecho- dzimy do dalszej części grafu. Aby wyznaczyć najkrótszą ścieżkę między s a wszystkimi innymi węzłami, w algorytmie Dijkstry wymaga się, aby w każdym węźle zapisywane były kolor i oszacowanie najkrótszej ścieżki. Zwykle oszacowanie najkrótszej ścieżki zapisuje się w zmiennej d. Początkowo wszystkim węzłom przypisujemy kolor biały, wszystkie oszacowania ścieżki ustawiamy na ∞, co oznacza wielkość dowolnie dużą, większą od wagi dowolnej krawę- dzi grafu. Oszacowanie najkrótszej ścieżki dla węzła początkowego ustawiamy na 0. Interfejs najkrótszych ścieżek 447 W miarę działania algorytmu, wszystkim węzłom poza początkowym przypisujemy rodzi- ców z drzewa najkrótszych ścieżek. Rodzic węzła może zmieniać się przed zakończeniem działania algorytmu wielokrotnie. Dalej algorytm Dijkstry działa następująco: najpierw spośród wszystkich białych węzłów grafu wybieramy węzeł u z najmniejszym oszacowaniem najkrótszej ścieżki. Wstępnie będzie to węzeł początkowy, którego ścieżka została oszacowana na 0. Po wybraniu węzła zaczerniamy go. Następnie, dla każdego białego węzła v przylegającego do u zwalniamy krawędź (u, v). Kiedy zwalniamy krawędź, sprawdzamy, czy przejście z u do v poprawi wyznaczoną dotąd najkrótszą ścieżkę do v. W tym celu dodajemy wagę (u, v) do oszaco- wania najkrótszej ścieżki do u. Jeśli wartość ta jest mniejsza lub równa oszacowaniu najkrót- szej ścieżki do v, przypisujemy tę wartość v jako nowe oszacowanie najkrótszej ścieżki i usta- wiamy v jako rodzica u. Proces ten powtarzamy dotąd, aż wszystkie węzły będą czarne. Kiedy wyliczone zostanie już drzewo najkrótszych ścieżek, najkrótszą ścieżkę z węzła s do danego węzła t można wybrać poprzez przejście po tym drzewie od węzła t przez kolejnych rodziców, aż do s. Ścieżka o odwrotnej kolejności do uzyskanej jest ścileżką szukaną. Na rysunku 16.3 pokazano wyznaczanie najkrótszej ścieżki z a do wszystkich innych węzłów grafu. Na przykład, najkrótsza ścieżka z a do b to 〈a, c, f, b〉, jej waga wynosi 7. Oszacowania najkrótszych ścieżek i ich rodziców pokazano obok poszczególnych węzłów. Oszacowanie najkrótszej ścieżki znajduje się na lewo od ukośnika, rodzic węzła na prawo. Krawędzie zaznaczone na szaro są krawędziami zmieniającego się drzewa najkrótszych ścieżek. Interfejs najkrótszych ścieżek shortest int shortest(Graph *graph, const PathVertex *start, List *paths, int (*match) (const void *key1, const void *key2)); Zwracana wartość: 0, jeśli wyznaczanie najkrótszej ścieżki się powiodło i –1 w przeciw- nym razie. Opis: Wylicza najkrótszą ścieżkę między start a wszystkimi pozostałymi węzłami grafu skierowanego z wagami graph. Operacja modyfikuje graph, więc w razie potrzeby należy zrobić jego kopię przed jej wywołaniem. Wszystkie węzły grafu muszą zawierać dane typu PathVertex. Wagę poszczególnym krawędziom przypisuje się przez nadanie wartości polu weight struktury PathVertex przekazanej do graph_ins_edge jako data2. Pola data poszczególnych struktur PathVertex używa się do zapisywania danych węzła, na przy- kład jego identyfikatora. Funkcja match grafu, przekazywana podczas inicjalizacji do graph_ init, używana jest do porównywania pól data. Jest to ta sama funkcja, która powinna być przekazana do shortest jako match. Kiedy najkrótsza ścieżka zostanie wyliczona, zwracana jest w liście paths, będącej listą struktur PathVertex. W paths rodzic węzła początko- wego ustawiany jest na NULL, zaś pole parent wszystkich pozostałych węzłów wskazuje 448 Rozdział 16. Algorytmy operujące na grafach Rysunek 16.3. Wyznaczanie za pomocą algorytmu Dijkstry. najkrótszych ścieżek węzeł poprzedzający dany węzeł na ścieżce zaczynającej się od węzła początkowego. Węzły z paths wskazują węzły należące do graph, wobec czego pamięć zajmowana przez te węzły musi być dostępna tak długo, jak długo korzystamy z paths. Potem do usunięcia paths używa się operacji list_destroy. Złożoność: O(EV2), gdzie V jest liczbą węzłów grafu, a E liczbą jego krawędzi. Można uzy- skać nieznaczną poprawę szybkości, w postaci wyniku O(E lg V), podobnie jak w przy- padku omawianego wcześniej algorytmu Prima. Implementacja najkrótszej ścieżki i analiza kodu 449 Implementacja najkrótszej ścieżki i analiza kodu Aby wyznaczyć najkrótsze ścieżki z danego węzła do wszystkich węzłów z niego dostęp- nych w skierowanym grafie z wagami, graf zapisujemy tak samo, jak zrobiliśmy to przy określaniu drzewa minimalnego, jednak zamiast struktury MstVertex używamy struktury PathVertex (listing 16.3). W strukturze tej możemy zapisać grafy z wagami oraz zapa- miętywać informacje o węzłach i grafach wymagane w algorytmie Dijkstry. Struktura ta ma pięć elementów: data to dane węzła, weight to waga krawędzi przylegającej do węzła, color to kolor węzła, d jest oszacowaniem najkrótszej ścieżki do węzła, a parent to rodzic węzła w drzewie najkrótszych ścieżek. Graf zawierający struktury PathVertex tworzymy tak samo, jak wcześniej tworzyliśmy graf zawierający sltruktury MstVertex. Listing 16.3. Implementacja wyliczania najkrótszych śc.ieżek /**************************************************l*************************** * l * * ------------------------------ shortest.c ------l------------------------ * * l * ***************************************************l**************************/ #include float.h #include stdlib.h #include graph.h #include graphalg.h #include list.h #include set.h /**************************************************l*************************** * l * * --------------------------------- relax --------l------------------------ * * l * ***************************************************l**************************/ static void relax(PathVertex *u, PathVertex *v, double weighlt) { /**************************************************l*************************** * l * * Zwolnienie krawędzi między węzłami u i v. l * * l * ***************************************************l**************************/ if (v- d u- d + weight) { v- d = u- d + weight; v- parent = u; } return; } /**************************************************l*************************** * l * * ------------------------------- shortest -------l------------------------ * * l * 450 Rozdział 16. Algorytmy operujące na grafach ***************************************************l**************************/ int shortest(Graph *graph, const PathVertex *start, Listl *paths, int (*match) (const void *key1, const void *key2)) { AdjList *adjlist; PathVertex *pth_vertex, *adj_vertex; ListElmt *element, *member; double minimum; int found, i; /**************************************************l*************************** * l * * Inicjalizacja wszystkich węzłów grafu. l * * l * ***************************************************l**************************/ found = 0; for (element = list_head( graph_adjlists(graph)); element != lNULL; element = list_next(element)) { pth_vertex = ((AdjList *)list_data(element))- vertex; if (match(pth_vertex, start)) { /********************************************l*************************** * l * * Inicjalizacja węzła początkowego. l * * l * *********************************************l**************************/ pth_vertex- color = white; pth_vertex- d = 0; pth_vertex- parent = NULL; found = 1; } else { /********************************************l******************
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Algorytmy w C
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: