dd.docx

6.algorytmem Kruskala 

W celu wykonania naszego zadania posłużymy się algorytmem Kruskala następnie dla porównania algorytmem Prima.

Pseudokod można zapisać następujący sposób:

1.                Sortuj krawędzie według wag.

2.                Wybierz krawędź z najniższą wagą, która nie tworzy cyklu w grafie oraz nie jest w zbiorze rozwiązania.

3.                Dodaj krawędź do zbioru rozwiązania.

4.                Jeżeli zbiór rozwiązania jest drzewem rozpinającym (zawiera wszystkie wierzchołki) przerwij działanie, w przeciwnym wypadku przejdź do pkt. 2.

Zacznijmy od pierwszego założenia, że dane krawędzie należy ułożyć w kolejności od tej, której waga jest najniższa do najwyższej wobec tego pierwszą krawędzią, jaką należałoby użyć w celu stworzenia drzewa jest krawędź między 3 i 4 z wagą 10, następnie łączymy wierzchołek 1 z 2 oraz 4 z 6 gdyż waga krawędzi między nimi wynosi 15. Kolejną operacją jest połączenie wierzchołków z wagą 30 a mianowicie 1 z 4 oraz 3 z 5. Następne połączenia między wierzchołkami nie są możliwe gdyż spowodowałyby one powstanie cyklu ponadto każdy wierzchołek został już wybrany. Sumujemy wagi na poszczególnych krawędziach w celu obliczenia, jaką minimalną liczbę metrów kabla potrzebujemy w celu sporządzenia sieci.

Identyczne minimalne drzewo rozpinające uzyskamy stosując algorytm Prima, który podobnie jak poprzedni jest opary o metodę zachłanną.

Pseudokod można zapisać następujący sposób:

1.            Wybierz wierzchołek startowy i dodaj do zbioru rozwiązań.

2.            Utwórz listę wszystkich wierzchołków połączonych z wierzchołkami ze zbioru rozwiązań.

3.            Z listy wybierz połączenie o najmniejszej wadze i dodaj wierzchołek do zbioru rozwiązań.

4.            Jeżeli zbiór rozwiązań zawiera wszystkie wierzchołki to koniec, w przeciwnym wypadku przejdź do pkt. 2.

Tworzymy jak w algorytmie Kruskala listę krawędzi z uporządkowanymi wagami następnie wybieramy wierzchołek, od którego chcemy rozpocząć tworzenie drzewa, czyli nie jesteśmy zmuszeni zacząć od wierzchołka, przy którym waga jest najmniejsza, dlatego też zaczniemy od 1. Z listy wag wybieramy wierzchołek łączący się z 1 o najmniejszej wadze krawędzi oraz nienależący do drzewa, czyli 2. Kolejnym krokiem jest poszukiwanie kolejnego wierzchołka wybieramy 4 z tego względu, że waga wynosi 30 natomiast np. z 2 do 5 wynosiłaby 40. Kolejno wybieramy wierzchołek 3 oraz wierzchołek 6 ostatnim etapem jest wybór wierzchołka 5 łączącego się z 3.

algorytmem Kruskala 

Na koniec rozważań o sposobach wyznaczania minimalnego drzewa rozpinającego przedstawiamy krótki i zwięzły przykład, który z pewnością rozwieje wszelkie wątpliwości, w jaki sposób tworzone jest MST poprzez algorytm Kruskala.

Przyjmijmy, że chcemy wyznaczyć MST dla poniższego grafu:

W pierwszym kroku należy posortować krawędzie grafu w porządku niemalejącym. Kolejność ta będzie przedstawiała się następująco (podajemy wagi tych krawędzi): 1, 4, 5, 6, 8, 14, 25, 28, 35, 41, 44, 45. Pamiętajmy, że każdy wierzchołek jest początkowo odrębnym drzewem. Algorytm ma za zadanie sprawdzać w kolejności sortowania poszczególne krawędzie. I tak:

Krawędź o wadze 1 połączyła dwa rozłączne drzewa w jedno (oznaczone etykietami 1 w wierzchołkach oraz niebieską krawędzią). Następnie sprawdzamy krawędź o wadze 4:

Końce tej krawędzi należą do różnych drzew, więc dodajemy ją do lasu rozpinającego. W kolejnym kroku sprawdzamy krawędź „5”:

Krawędź ta łączy dwa drzewa (będące wierzchołkami) i tworzy jedno drzewo o wierzchołkach, w których widnieją etykiety o wartości 2. Dalej należy rozpatrzyć, czy krawędź o wadze 6 należy włączyć do lasu rozpinającego.

Okazuje się, że tak – krawędź „6” łączy dwa drzewa – jedno z etykietami 1, a drugie z etykietami 2. W ten sposób powstaje jedno drzewo o etykietach wierzchołków równych 2. Następna krawędź na posortowanej liście - to krawędź o wadze 8. Gdybyśmy dodali ją do drzewa rozpinającego, powstałby cykl – a zatem odrzucamy ją i sprawdzamy kolejną krawędź – „14”. Dzięki niej można połączyć drzewo „2” z innym, jednowierzchołkowym drzewem – tym samym krawędź zostaje dodana do drzewa rozpinającego.

Następne w „kolejce” do sprawdzenie są krawędzie 25 oraz 28. Dodanie każdej z nich spowoduje utworzenie cyklu w drzewie „2”, a więc nie bierzemy ich pod uwagę. Algorytm przechodzi do krawędzi o wadze 35. Ponieważ łączy ona dwa wierzchołki należące do pojedynczych drzew, „akceptujemy” ją i tworzymy nowe drzewo o etykietach „3”.

Przechodzimy do krawędzi „41” – utworzyłaby ona cykl w drzewie „2”, więc opuszczamy ją i sprawdzamy przydatność krawędzi „44”. Dzięki niej możemy połączyć drzewo „2” i „3”, w związku z tym dodajemy ja do drzewa rozpinającego.

Ostatnią krawędzią na liście jest łuk o wadze 45. Nie trafia on jednak do drzewa rozpinającego, gdyż za jego sprawą powstałby niepożądany cykl.

Na tym kończy się działanie algorytmu. Powyższy rysunek potwierdza, że zostało utworzone minimalne drzewo rozpinające – wszystkie wierzchołki grafu zostały włączone do jednego wspólnego drzewa i żaden węzeł nie pozostał odosobniony. Całkowita suma wszystkich wag krawędzi należących do MST jest równa 109 i jest to minimalna wartość dla tego grafu.

Prima

   .

5.

4

Lista sasiedzctwa

Macierz sąsiedztwa

Macierz Incedynecji

Procedury przeglądania grafu w głąb (DFS) i wszerz (BFS) są bardzo często wykorzystywane w innych, bardziej złożonych algorytmach (np. badania spójności).
W strategii DFS wybrany wierzchołek należy umieścić na stosie, zaznaczyć jako odwiedzony a następnie przejść do jego następnika. Następnik również umieszczamy na stosie, zaznaczamy jako odwiedzony przechodzimy do jego następnika. Jak widać procedurę można wywoływać rekurencyjnie. Jeśli dojdziemy do takiego wierzchołka, że nie ma on krawędzi incydentych z nieodwiedzonymi wierzchołkami, należy usunąć go ze stosu i pobrać ze stosu kolejny wierzchołek do przeszukania. W praktyce stosuje się zasadę, że jeśli przeszukiwany wierzchołek jest połączony krawędziami z wieloma wierzchołkami, wybiera się do przeszukania wierzchołek o najmniejszej liczbie porządkowej. Dlatego szukając kolejny nieodwiedzony następnik należy rozpoczynać od końca macierzy. Przeszukiwanie DFS wykorzystuje się do badania spójności grafu. Jeśli procedura wywołana dla pierwszego wierzchołka "dotrze" do wszystkich wierzchołków grafu to graf jest spójny. 
Aby przeszukać graf wszerz (BFS) należy zamiast stosu wykorzystać kolejkę do przechowywania wierzchołków a kolejnych nieodwiedzonych następników szukać od początku macierzy. 
Oto przykładowy graf:

W głąb:

Przeszukiwanie w głąb (DFS):
Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy na stos wszystkie jego następniki, w kolejności od tego z największym indeksem:
Odwiedzone: 1; Stos: 3, 2;
Bierzemy wierzchołek ze stosu, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone jeszcze następniki na stos:
Odwiedzone: 1, 2; Stos: 3, 5, 4;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:
Odwiedzone: 1, 2, 4; Stos: 3, 5;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:
Odwiedzone: 1, 2, 4, 5; Stos: 3;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 3 jest 6, ten wierzchołek jeszcze nie jest odwiedzony więc wrzucamy go na stos:
Odwiedzone: 1, 2, 4, 5, 3; Stos: 6;
Bierzemy wierzchołek ze stosu, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma czego wrzucić na stos:
Odwiedzone: 1, 2, 4, 5, 3, 6; Stos: ;
Stos jest pusty zatem zakończyliśmy przeszukiwanie grafu w głąb.

Przeszukiwanie wszerz:

Przeszukiwanie w szerz (BFS):
Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy do kolejki wszystkie jego następniki, w kolejności od tego z najmniejszym indeksem:
Odwiedzone: 1; Kolejka: 2, 3;
Bierzemy wierzchołek z kolejki, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone jeszcze następniki do kolejki:
Odwiedzone: 1, 2; Kolejka: 3, 4, 5;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 3 jest 6 więc wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3; Kolejka: 4, 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3, 4; Kolejka: 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3, 4, 5; Kolejka: 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma czego wrzucić do kolejki:
Odwiedzone: 1, 2, 3, 4, 5, 6; Kolejka: ;
Kolejka jest pusta zatem zakończyliśmy przeszukiwanie grafu w szerz.

3 Kod Huffmana

Klasyczny algorytm wyznaczania słów kodowych bazuje na drzewie binarnym. Załóżmy, że w strumieniu wejściowym występują 8-bitowe liczby całkowite, tzn. dane typu „unsigned...