Co to jest drzewo algorytmu?

Drzewa to jedne z najważniejszych

struktur danych w informatyce. Można

je wykorzystać do wielu celów, min. do

graficznej reprezentacji hierarchii,

sortowania, itd.

Każde drzewo składa się z wierzchołków (węzłów) ,oraz

łączących je krawędzi.

Każdy wierzchołek może posiadać wielu przodków i

potomków.

Potomkowie „bezpośredni” to dzieci wierzchołka, a

przodek bezpośredni to ojciec (każdy wierzchołek ma

dokładnie jednego ojca).

Drzewo może posiadać wiele dzieci, choć są drzewa o ich

określonej liczbie, np. binarne.

Wierzchołki drzewa reprezentują konkretne dane

(liczby, napisy albo bardziej złożone struktury danych).

Odpowiednie ułożenie danych w drzewie może ułatwić i

przyspieszyć ich wyszukiwanie.

-

Pierwszy obiekt zwany jest korzeniem

- Liście są to węzły nie mające potomstwa

- Droga w drzewie to sekwencja węzłów w drzewie

odpowiadających przejściu od jednego wierzchołka do

drugiego, po krawędziach łączących je

- Długość ścieżki od korzenia do danego węzła nazywamy

głębokością danego węzła w drzewie

- Największa głębokość węzła w drzewie jest wysokością

tego drzewa

Przykładem szczególnym drzewa jest tzw.

jako najpopularniejsza i najczęściej używana w procesie

rozwiązywania problemów algorytmicznych forma

***

posiada ono tę właściwość, że każdy węzeł może mieć

maksymalnie 2 dzieci, (prawe i lewe)

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Korzeń

Liście

W

ęz

ły

w

ew

nę

tr

zn

e

Przykład drzewa

binarnego

Struktura drzewa binarnego przypomina w dużym stopniu

strukturę poznanej już listy jednokierunkowej

W przypadku listy operowaliśmy wskaźnikiem

Następny

W przypadku drzew binarnych, zastępujemy ten wskaźnik

dwoma:

Lewy oraz Prawy

będącymi operatorami wskazującymi na odpowiednio lewą i

prawą stronę drzewa binarnego

Tablicowa reprezentacja drzewa

binarnego

Węzeł

Syn

Ojciec

1

2;53

1

2

4;5

1

3

6;7

1

4

8;9

2

5

10;11

2

6

12;13

3

7

14;15

3

…

…

…

Przykład zastosowania drzewa binarnego do

reprezentacji wyrażenia arytmetycznego

*

+

12.5

+

*

2

3

7

9

Liście = wartości

Węzły wewnętrzne= operatory

Krok I 2+3=5

Krok II 7*9=63

Krok III 5+63=68

Krok IV 68*12.5=850

W kolejnych krokach dwa liście o najbliższym stopniu pokrewieństwa

rozpatrywane są wraz ich ojcem jako podstawowe wyrażenie do obliczenia.

Takie poddrzewo staje się liściem o obliczonej wcześniej wartości i schemat

powtarza się do momentu zastosowania wszystkich liści.

Typedef struckt
{

double val;
char op;

}

Int main()
{

STOS<wyrazenie*> s; // będzie zapamiętywał wskaźniki do rekordów

// w kolejności FILO co zostało omówione poprzednio

Val t[9]={{2,’0’}, {3,’0’}, {9,’+’}, {7,’0’}, {9,’0’}, {0,’*’},

{0,’+’}, {12.5,’0’}, {0,’*’}};

// tablica zawierająca operatory i operandy (wartości)

wyrazenie *x; // tworzymy wskaźnik x o typie „wyrazenie”

(węzeł)

For(int i=0; i<9; i++) // pętla odczytuje po kolei elementy tablicy

// analizując jej zawartość pod kątem znalezienia

// operatorów bądź wartości

{

x= new wyrazenie;
if ((t[i].op==‘*’ || t[i].op==‘+’ || t[i].op==‘-’ || t[i].op==‘:’

||t[i].op==‘/’))

x->op = t[i].op // jeśli element tablicy zawiera operator to x

// wskazuje operator, a temu operatorowi zostaje

// przypisany znak operatora

else

// w przeciwnym razie x będzie wskazywał na wartość,

{

// a operator jest „zerowany”

x-> val=t[i].val;
x-> op=‘0’;
}

x->lewy =NULL;

// inicjujemy komórki pamięci czyli lewą i

x->prawy=NULL;

// prawą gałąź, które są potomkami

węzła x

if((t[i].op==‘*’|| t[i].op==‘+’||t[i].op==‘-’

|| t[i].op==‘:’ ||t[i].op==‘/’))

{

wyrazenie *l1, *p1; // tworzymy wskaźniki gałęzi
s.pop(l1);

// na stos wrzucamy lewą gałąź

s.pop(p1); // na stos wrzucamy prawą gałąź
x->lewy =l1; // lewej gałęzi węzła x przypisujemy l1
x->prawy =p1; // prawej gałęzi węzła x przypisujemy p1

}

s.push(x); // zdejmujemy ze stosu w wiadomej kolejności

}

//w tym miejscu następuje wypisanie elementów stosu oraz obliczenie wyrażenia
//podanego w Odwrotnej Notacji Polskiej, a mianowicie: *12.5+*97+32=850

}

Wynik : (12.5*((9*7)+(3+2)))=850

Ujmując to „po ludzku”

funkcja wypisująca drzewo pod koniec przytoczonego

przykładu pozwala wyrazić się prostym algorytmem

rekurencyjnym (wywołującym siebie samego):

wypisz(w)
{

jeśli wyrażenie w jest liczbą, to wypisz ją;
jeśli wyrażenie jest operatorem op, to wypisz je
w kolejności:

(wypisz(w->lewy) op wypisz(w->prawy))

}

Grafy

Graf to – w uproszczeniu – zbiór wierzchołków, które
mogą być połączone krawędziami, w taki sposób, że
każda krawędź kończy się i zaczyna w którymś z
wierzchołków. Grafy to podstawowy obiekt rozważań
teorii grafów.

Za pierwszego teoretyka i badacza grafów uważa się

Leonarda Eulera, który rozstrzygnął zagadnienie

mostów królewieckich.

Problem mostów w Królewcu

Euler w 1736 roku

rozwiązał

problem, który

nurtował

mieszkańców

Królewca, a

mianowicie, jak

przejść przez

wszystkie siedem

mostów nie

przechodząc dwa

razy przez ten

sam.

Ostatecznie Euler doszedł do wniosku, iż problem jest nie

do rozwiązania, a przyczyną jest takie, a nie inne

rozmieszczenie mostów.

Uproszczony schemat problemu

mostów

(po

prawej)

daje

pierwsze pojęcie o tym jak i co

reprezentują grafy. Czerwone

kropki,

oznaczające

węzły,

reprezentują pewne obiekty (w

tym przypadku ląd), a krawędzie

łączące ze sobą wierzchołki

stanowią reprezentację relacji

zachodzących

pomiędzy

obiektami (w naszym przypadku

są to mosty).

Pojęcia podstawowe



Grafem G nazywamy parę(X,V), gdzie X oznacza zbiór

węzłów (wierzchołków), a V jest zbiorem określonych

krawędzi łączących wierzchołki z X



Graf jest skierowany jeśli jego krawędziom został

zadany kierunek (najczęściej oznaczany na rysunkach

przez strzałkę)



Jeśli rozpatrujemy dany przykład X→Y to węzeł X jest

węzłem początkowym

, a węzeł Y jest

węzłem

końcowym

Pojęcia c.d.



Stopniem wejściowym wierzchołka grafu nazywamy

liczbę krawędzi dochodzących do wierzchołka i

analogicznie…



Graf jest spójny jeśli każde dwa wierzchołki połączone

są drogą



Stopniem wyjściowym wierzchołka grafu nazywamy

liczbę krawędzi wychodzących od danego wierzchołka



Grafem regularnym nazywamy graf, w którym

wszystkie wierzchołki posiadają ten sam stopień

Pojęcia c.d.



Drogą (lub ścieżką) grafu nazywamy ciąg

wierzchołków, w którym każde dwa kolejne

wierzchołki (elementy tego ciągu) połączone są

krawędzią



Grafem zredukowanym G bądź podgrafem grafu G

nazywamy graf, którego elementy stanowią podzbiór

zbioru elementów grafu G (tzn. wierzchołki podgrafu

grafu G stanowią podzbiór zbioru wierzchołków grafu

G i odpowiednio krawędzi grafu zredukowanego G

stanowią podzbiór zbioru krawędzi grafu G)

Przykład normalizacji grafu

Rysunek jest niezgodny z definicją (istnieje tylko

jedna możliwa krawędź łącząca dwa wierzchołki w

dany sposób). Problem rozwiązywany jest poprzez

dołączenie dodatkowych wierzchołków:

X

Y

X

Y

Z

Plan skonstruowania

dwóch dróg X→Y

został zrealizowany

Sposoby reprezentacji grafów

-reprezentacja tablicowa

Jest to jedna z dwóch najpopularniejszych metod

reprezentacji grafu. Polega na stworzeniu tablicy

kwadratowej o wymiarach n x n, gdzie n oznacza

liczbę węzłów. Tablica w takiej implementacji

ukazywać będzie związek (krawędź) pomiędzy

poszczególnymi węzłami. W zależności od widzimisię

programisty, kolumna węzłów może reprezentować

ojców, a wiersz synów lub na odwrót lecz musi on

(programista) pozostać konsekwentny.

Przykład reprezentacji grafu w formie tablicowej

A

B

C

D

F

E

A

B

C

D

E

F

A

X

B

X

X

C

X

X

D

X

X

E

X

F

Po

pr

ze

dn

ik

i

-

O

jc

ow

ie

Następniki - Synowie

Tablica pokazuje po prostu, że węzeł A ma krawędź skierowaną do B, B

ma krawędzie skierowane do C i do D, zaś C do samego siebie oraz do E

itd.

Sposoby reprezentacji grafów

-słownik węzłów

Jest to druga najpopularniejsza metod reprezentacji

grafu polegająca na stworzeniu listy wskaźników do

list węzłów. Podstawową cechą słownika węzłów jest

opieranie się podczas wyszukiwania połączenia na

węźle wyjściowym, który wskazuje na dane. Lista

może (tak jak w przypadku tablic) działać

dwukierunkowo. Wskaźnik może wskazywać zarówno

na poprzedniki węzła (czyli węzły, od których

krawędzie dochodzą do opisywanego wskaźnika) jak i

następniki (węzły, które połączone są krawędziami

wychodzącymi od wskaźnika)

Przykład reprezentacji grafu w formie słownika węzłów

A

B

C

D

F

E

A B
B C, D
C C, E
D E, F
E F
F NULL

A NULL
B A
C B, C
D B
E C, D
F D, E

Lista następników

danego węzła

Lista poprzedników

danego węzła

Użycie słownika węzłów jest korzystniejsze niż tablic ze względu na

możliwość dynamicznej rozbudowy grafu bez obawy przepełnienia stosu z

czym trzeba się liczyć w przypadku dużej dynamicznej tablicy.

Przeszukiwanie grafu „w głąb”

Ten typ przeszukiwania grafu charakteryzuje

przechodzenie się po jego elementach w ramach raz

obranej drogi. Nazywa się to maksymalną eksploatacją

raz obranej drogi przed ewentualnym wybraniem

następnej. Ważne jest zapamiętywanie w programie

wierzchołków już raz odwiedzonych aby nie

wstępować drugi raz do już odwiedzonego węzła.

Przykład

A

E

B

D

G

F

C

Lista wierzchołków sąsiadujących

A: B, E, D

B: A, C, E

C: B, G

D: A, E, G

E: A, B, D, F

F: E

G: C, D

Algorytm przeszukiwania „w głąb” rozpocznie się od wierzchołka A. zapamięta go

jako już odwiedzony i rozpatrzy jedną z trzech dróg: B, E lub D. Na początek

wybierze wierzchołek B, zapamięta go jako odwiedzony i rozpatrzy jego węzły

sąsiadujące czyli: A, C, E. Ponieważ A został już odwiedzony, skierujemy się do

wierzchołka C. Stamtąd jedyną drogą jest G. Z G z kolei możemy skierować się

jedynie do D. Ponieważ A i G są już „odwiedzone” jedyną ścieżką pozostaje

krawędź w kierunku węzła E, a potem do F. Droga przebyta przez algorytm

prezentuje się następująco: A →B →C →G →D →E →F.

Przeszukiwanie grafu „wszerz”

A

E

B

D

G

F

C

Przeszukiwanie „wszerz” opiera się na badaniu

grafu na jednej głębokości. Kolokwialnie można

powiedzieć, że algorytm „wszerz” idzie „ławą”.

Dla przykładu posłużymy się takim samym grafem

jak w przypadku przeszukiwania „w głąb”.

W tym przypadku zaczynamy również od wierzchołka A. Badamy jego węzły

sąsiadujące czyli B, D i E. Następnie algorytm przeszukuje nieodwiedzonych

przez nasz algorytm sąsiadów tych węzłów czyli C, G i F. W efekcie droga

przeszukiwania odbyła się następująco: A, B, D, E, C, G, F.

Cykle w grafach

Definicja: Cyklem nazywamy drogę w grafie, która

rozpoczyna się i kończy w tym samym wierzchołku

Cykl skierowany to cykl, w którym wierzchołki są

uporządkowane zgodnie z kierunkiem krawędzi

łączących poszczególne pary

Jeśli graf skierowany nie zawiera ani jednego cyklu

skierowanego nazywamy go acyklicznym grafem

skierowanym

Dlaczego acykliczny graf skierowany dotyczy jedynie

grafów skierowanych?

Odpowiedź jest bardzo prosta. Każdy graf

nieskierowany

możemy zaprezentować jako graf skierowany w

obu kierunkach

co czyni z tego grafu, graf zawierający cykl skierowany

X

Y

X

Y

Cykl Hamiltona

Jeśli droga cyklu, którą obraliśmy, przechodzi przez

każdy z wierzchołków dokładnie raz, to taki cykl

nazywamy cyklem Hamiltona – od nazwiska słynnego

irlandzkiego matematyka, który w ogromnym stopniu

przyczynił się do rozwoju teorii grafów

Cykl Hamiltona- przykład

A

E

F

B

C

D

G

H

I

J

Podążając

alfabetycznie, w

grafie

nieskierowanym, od

wierzchołka A do J (i

następnie do A)

przechodzimy przez

wszystkie wierzchołki

dokładnie jeden raz (i

kończąc na

wierzchołku

początkowym)

udowadniając, że

dany graf stanowi

cykl Hamiltona.

A

H

I

J

F

G

B

C

D

E

Ten sam graf (o tej

samej strukturze)

możemy „przejść”

również w taki

sposób.

Podążajmy po raz

kolejny

alfabetycznie od A

do J.

A

H

G

F

E

D

J

I

C

B

Ale również w ten

sposób, stosując

znaną metodę.

Problem komiwojażera

Z cyklem Hamiltona związany jest słynny problem
optymalizacji drogi zwany problemem komiwojażera.
Zadaniem, jakie stoi przed bohaterem problemu, jest
jednokrotne zawitanie do każdego z miast zaplanowanych
do odwiedzenia przy minimalizacji wysiłku (kosztów,
długości drogi itp.). Możemy przyjąć np., że miasta dzieli
pewna

odległość

lub

koszt

przejazdu

między

poszczególnymi miastami różni się itd. w zależności od
minimalizowanej cechy.

Problem komiwojażera c.d.

Nowy

Jork

Chicago

Los

Angeles Seattle

Nowy

Jork

0

400

750

900

Chicago

400

0

650

350

Los

Angeles

750

650

0

200

Seattle

900

350

200

0

Przykładow

e ceny lotów

pomiędzy

miastami w

USA

NY

C

LA

S

400

750

200

650

900

350

NY→S→C→LA→NY = 900+350+650+750 = 2650
NY→S→LA→C→NY = 900+200+650+400 = 2150

NY→C→S→LA→NY = 400+350+200+750 = 1700

NY→C→LA→S→NY = 400+650+200+900 = 2150
NY→LA→S→C→NY = 750+200+350+400 = 1700

NY→LA→C→S→NY = 750+650+350+900 = 2650

Wyruszamy z Nowego Jorku i

tam też chcemy wrócić po

odwiedzeniu Chicago, Seattle

i Los Angeles (w dowolnej

kolejności. Jak wybrać trasę?

Z obliczeń wynika

jasno, że najtaniej

zrealizujemy naszą

podróż lecąc do LA,

potem do Seattle, a

następnie do Chicago i

z powrotem do NY

(lub na odwrót)

A co jeśli nasz graf ma dziesięć wierzchołków i wygląda tak?

Ile różnych cykli Hamiltona zawiera taki graf?

Otóż pierwszą krawędź cyklu można wybrać na 9 różnych

sposobów, ponieważ każdy wierzchołek grafu jest

połączony krawędzią z pozostałymi dziewięcioma. Po

wyborze pierwszej krawędzi pozostaje nam 8 możliwych

wyborów, później 7, 6 5 ... 1. W efekcie otrzymujemy liczbę

cykli Hamiltona równą:

L

H

= 9 • 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 = 9! = 362880

Dla n wierzchołków:

L

H

= (n - 1) • (n - 2) • ... • 3 • 2 • 1 = (n - 1)!

Implementacja C++

#include <iostream>

#include <list>

 

using namespace std;

 

const int MAXV = 50; // maksymalna liczba wierzchołków

const int MAXINT = 2147483647; // maksymalna, dodatnia liczba

//całkowita

 

 

// ++++++++ konstruujemy strukturę krawędzi z wagą

 

struct edge

{

int v,d; // v to numer wierzchołka, a d to suma wag

};

// +++++++++++ wprowadzamy zmienne globalne

 

int n,m,d,dh; // n i m to liczba wierzchołków i krawędzi w grafie

// d i dh to odpowiednio suma wag dla cyklu oraz

// bieżąca suma wag

 

list <edge> L[MAXV + 1]; // deklarujemy listę tablic o dwóch zmiennych ze

// struktury edge i maksymalnej długości = 50,

// Każdy element tablicy jest z kolei listą

// wierzchołków oraz wag krawędzi prowadzących do

// tych wierzchołków: {v, d}

 

list <int> q,qh; // tworzymy listę odwiedzonych wierzchołków

// bieżącą i ogólną

bool visited[MAXV + 1]; // oraz warunek logiczny, który zapamięta czy dany

// wierzchołek był odwiedzony



// tworzymy funkcję rekurencyjną (czyli wywołującą samą siebie)



// przeszukiwania w głąb o nazwie TSP



 



void TSP(int v)



{



qh.push_back(v); // dorzucamy do listy odwiedzonych wierzchołków



// numer wierzchołka



 



if(qh.size() == n) // jeśli rozmiar listy równa się zadanej ilości



// wierzchołków, czyli odwiedzone zostały już



// wszystkie to:



{



for(list<edge>::iterator i = L[v].begin(); i != L[v].end(); i++)



 



// wykonujemy pętlę przesuwając iterator (swego rodzaju kursor, wskaźnik)

po



// kolejnych pozycjach listy zawierającej numery wierzchołków oraz wagi



// krawędzi prowadzących wierzchołka v



 



if(i->v == 1) // warunek, istnienia krawędzi od v do

pierwszego



// wierzchołka czyli „czy dla danego v iterator = 1”



// jeśli tak, to…



{



dh += i->d; // do bieżącej sumy wag doda się waga

wskazanej



// przez iterator krawędzi oraz…



 



if(dh < d) // oraz wykona się warunek logiczny



// sprawdzający czy bieżąca suma wag jest



// mniejsza od znanej już sumy wag krawędzi



{



d = dh; // jeśli tak, to bieżąca suma stanie się



// najmniejszą sumą dotychczas poznaną



// na odcinku od początkowego



// wierzchołka do obecnie sprawdzanego



 



q.assign(qh.begin(), qh.end());



// wtedy to zapamiętujemy



// kolejność wierzchołków



// od pierwszego do bieżącego



 



q.push_back(1); // zamykamy cykl dopisując do kolejki

v=1



}



dh -= i->d; // w przeciwnym razie od zwiększonego



// wcześniej dh o daną wagę odejmiemy ją

i



// wrócimy do sumy wag z poprzedniej

pętli



break;



}



}

Jeszcze trochę…



else // jeśli jednak lista kolejnych wierzchołków nie osiągnęła



// rozmiaru zadanej ilości wierzchołków to…



 



{



visited[v] = true; // oznaczamy wierzchołek v jako już

// odwiedzony



 



for(list<edge>::iterator i = L[v].begin(); i != L[v].end(); i++)



 



// wykonujemy pętlę dla każdego sąsiada



// wierzchołka v



 



if(!visited[i->v]) // jeśli “sąsiad” nie był odwiedzony to…



 



{



dh += i->d;

// zwiększamy sumę wag ścieżki



TSP(i->v);

// wywołujemy poszukiwanie cyklu (czyli listy



// kolejnych wierzchołków dla której suma wag



// jest najmniejsza)



 



dh -= i->d; // odejmujemy od sumy wag tę ostatnią wagę



// krawędzi aby w nowej pętli odwoływać się do

// poprzedniej



}



visited[v] = false; // kończymy pracę z tym wierzchołkiem oraz…



}



qh.pop_back(); // usuwamy wierzchołek z listy



}



//wykonujemy główną funkcję poszukującą najkorzystniejszego

cyklu //Hamiltona



 



main()



{



 



// Odczytujemy definicję grafu ze standardowego wejścia



 



cin >> n >> m;



 



for(int i = 1; i <= m; i++)



{



int v,w,dx; cin >> v >> w >> dx;



edge x;



x.v = w; x.d = dx; L[v].push_back(x);



x.v = v; L[w].push_back(x);



}



cout << endl;



// Rozpoczynamy wyszukiwanie cyklu Hamiltona



// o najmniejszej sumie wag krawędzi



 



for(int i = 1; i <= n; i++)



{



visited[i] = false;

// zerujemy odwiedziny



q.clear(); qh.clear();

// zerujemy kolejki



d = MAXINT; dh = 0;

// przypisujemy nieskończoność

// do d, a do sumy wag 0



TSP(i);

// wyszukujemy cykl Hamiltona

}

// zaczynając od wierzchołka 1

do

// n-tego



// Wypisanie wyników



 



if(q.size())

// jeśli cykl został znaleziony wypisujemy:



 



{



cout << "CYKL HAMILTONA : ";



for(list<int>::iterator i = q.begin(); i != q.end(); i++)



cout << (* i) << " ";



cout << "\n SUMA WAG WYNOSI : " << d << endl;



}



// jeśli jednak nie ma cyklu to wypiszemy:



 



else cout << "GRAF NIE POSIADA CYKLU HAMILTONA\n";



 



cout << endl;



system("PAUSE");



}



 



Koniec programu.

Cykl Eulera

Bardzo podobnym do cyklu Hamiltona problemem

(często z resztą mylonym z nim) jest cykl Eulera. W

cyklu Hamiltona dany wierzchołek odwiedzony był

dokładnie raz, natomiast w przypadku Eulera tą

„jednorazowością” charakteryzują się krawędzie.

Innymi słowy: Hamilton pokazuje jak jednorazowo

znaleźć się na każdym z brzegów, a Euler, jak przejść

dokładnie jeden raz przez każdy z mostów.

Oczywiście w przypadku podanego już przykładu

mostów królewieckich nie znajdujemy ani cyklu

Eulera, ani Hamiltona

Twierdzenie Eulera

Graf nieskierowany zawiera cykl Eulera, jeśli jest

spójny i jego wierzchołki mają parzysty stopień. W

przypadku grafu skierowanego, zawierającego cykl

Eulera, oprócz spójności musi występować taki sam

stopień wyjściowy i wejściowy dla każdego

wierzchołka.

Dzięki tej definicji jesteśmy w stanie odpowiedzieć

na pytanie dlaczego mostów w Królewcu nie da się

przejść jednocześnie wszystkich jeden raz. Na

rysunku dokładnie widać, że nie jest spełniony

warunek parzystości stopnia wierzchołków.

Algorytm Fleury’ego

Ten algorytm jest uzupełnieniem twierdzenia Eulera

ponieważ, pozwala odszukać cykl Eulera w momencie

gdy samo twierdzenie pozwala jedynie stwierdzić jego

istnienie. Jest on opisany w prosty sposób:

1. Wybierz początkowy węzeł

2. Wybierz dowolną , nieprzechodzoną jeszcze krawędź spośród

krawędzi wychodzących z wierzchołka, w którym aktualnie się

znajdujemy. Dodatkowo postaraj się nie wybierać krawędzi

tzw. Cięcia grafu czyli takiej krawędzi, której usunięcie

podzieliłoby graf (chyba że nie ma wyboru)

3. Przejdź przez wybraną krawędź do następnego wierzchołka

4. Zapamiętaj wybraną krawędź i usuń ją z grafu

5. Powtarzaj kroki 2, 3 i 4 aż do momentu przejścia wszystkich

krawędzi i powrotu do wierzchołka początkowego

D

F

C

G

B

A

E

D

F

C

G

B

A

E

D

F

C

G

B

A

E

D

F

C

G

B

A

E

D

F

C

G

B

A

E

Dziękuję za uwagę!

Zachęcam do zgłębiania fascynującego tematu jakim są zagadnienia

algorytmiki, a który w bardzo okrojonym stopniu próbowałem

Państwu przedstawić.

Prezentacja oparta została w dużej mierze na książce Piotra

Wróblewskiego pt.: Algorytmy, struktury danych i techniki

programowania oraz na stronach:

http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol027.php

http://www.adaptivebox.net/CILib/code/tspcodes_link.html
http://pl.wikipedia.org

Niektóre użyte sformułowania są dosłownymi cytatami lub są

bardzo zbliżone do cytowanych fragmentów ww. źródeł. Brak

oznaczenia w każdym z miejsc powodowany był przejrzystością

prezentacji. Jednocześnie chciałbym zaznaczyć, że użyte cytaty

czy kody źródłowe w najlepszy możliwy sposób opisywały

omawiane zagadnienia, w związku z czym pozwoliłem sobie na

dosłowne ich skopiowanie. Tam gdzie uznałem za zasadne i

możliwe, formułowałem zdania we własnym zakresie.