Teoretyczne podstawy informatyki
Wykład 7:
Grafowy model danych
29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs 1
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Graf
pð Graf to jest relacja binarna.
pð Dla grafów mamy ogromne możliwoÅ›ci wizualizacji jako zbiór
punktów (zwanych wierzchołkami) połączonych liniami lub
strzałkami (nazwanych krawędziami). Pod tym względem graf
stanowi uogólnienie drzewiastego modelu danych.
pð Podobnie jak drzewa, grafy wystÄ™pujÄ… w różnych postaciach:
grafów skierowanych i nieskierowanych lub etykietowanych
i niezaetykietowanych.
pð Grafy sÄ… przydatne do analizy szerokiego zakresu problemów:
obliczanie odległości, znajdowanie cykliczności w relacjach,
reprezentacji struktury programów, reprezentacji relacji
binarnych, reprezentacji automatów i układów elektronicznych.
2 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Relacje
pð Chociaż zaÅ‚ożyliÅ›my, że w ogólnoÅ›ci elementy należące do zbiorów sÄ…
niepodzielne, w praktyce często korzystnym rozwiązaniem jest przypisanie
elementom pewnych struktur.
pð WażnÄ… strukturÄ… dla elementów jest lista o staÅ‚ej dÅ‚ugoÅ›ci zwana krotkÄ….
pð Każdy element takiej listy nazywamy skÅ‚adowÄ… krotki.
pð Zbiór elementów, z których każdy jest krotkÄ… o takiej samej licznoÅ›ci 
powiedzmy k - nazywamy relacją. Licznością takiej relacji jest k.
pð JeÅ›li liczność wynosi 2 mówimy o krotce lub relacji binarnej.
pð Iloczyn kartezjaÅ„ski A x B:
Jest to zbiór par, z których pierwszy element pochodzi ze zbioru A, drugi ze
zbioru B, czyli
A x B = { (a, b) : a Îð A oraz b Îð B}
Iloczyn kartezjaÅ„ski nie ma wÅ‚asnoÅ›ci przemiennoÅ›ci, A x B Ä…ð B x A
K-elementowy iloczyn kartezjański A1 x A2 x A3 & x Ak to zbiór k-krotek
(a1,a2, & , ak).
3 29.11.2011
3 24.11.2009
Prof. dr hab. Elżbieta Richter-Wąs
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Podstawowe pojęcia
pð Graf skierowany (ang. directed graph)
Składa się z następujących elementów:
Zbioru V wierzchołków (ang. nodes, vertices)
Relacji binarnej E na zbiorze V. Relacje E nazywa się zbiorem krawędzi
(ang. edges) grafu skierowanego. Krawędzie stanowią zatem pary
wierzchołków (u,v).
0 1
V = {0,1,2,3,4}
E = { (0,0), (0,1), (0,2), (1,3), (2,0), (2,1),
2 3
(2,4), (3,2), (3,4), (4,1) }
4
4 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Podstawowe pojęcia
pð Etykiety:
Podobnie jak dla drzew, dla grafów istnieje możliwość przypisania do
każdego wierzchołka etykiety (ang. label).
Nie należy mylić nazwy wierzchołka z jego etykietą. Nazwy wierzchołków
musza być niepowtarzalne, ale kilka wierzchołków może być
oznaczonych ta sama etykieta.
gryzie
1 2
pies kot
pð Drogi:
Droga (ang. path) w grafie skierowanym stanowi listę wierzchołków,
(n1, n2, & , nk) taka, że występuje krawędz
łącząca każdy wierzchołek z
nastÄ™pnym, to znaczy (ni, ni+1) Îð E dla i=1, 2, & , k. DÅ‚ugość (ang. lengh)
drogi wynosi k-1, co stanowi liczbę krawędzi należących do tej samej
drogi.
5 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Podstawowe pojęcia
pð Grafy cykliczne i acykliczne:
Cykl (ang. cycle) w grafie skierowanym jest drogą o długości 1 lub więcej,
która zaczyna się i kończy w tym samym wierzchołku.
Długość cyklu jest długością drogi. Cykl jest prosty (ang. simple) jeżeli
żaden wierzchołek (oprócz pierwszego) nie pojawia się na nim więcej niż
raz.
Jeżeli istnieje cykl nieprosty zawierający wierzchołek n, to można znalez
ć
prosty cykl który zawiera n. Jeżeli graf posiada jeden lub więcej cykli to
mówimy ze jest grafem cyklicznym (ang. cyclic). Jeśli cykle nie występują
to, graf określa się mianem acyklicznego (ang. acyclic).
0 1
Przykłady cykli prostych:
(0,0), (0,2,0), (1,3,2,1), (1,3,2,4,1)
2 3 Przykład cyklu nieprostego:
(0,2,1,3,2,0)
4
6 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Grafy wywołań
pð WywoÅ‚ania dokonywane przez zestaw funkcji można reprezentować za
pomocą grafu skierowanego, zwanego grafem wywołań. Jego wierzchołki
stanowią funkcje, a krawędz
(P, Q) istnieje wówczas, gdy funkcja P wywołuje
funkcje Q.
pð Istnienie cyklu w grafie implikuje wystÄ™powanie w algorytmie rekurencji.
pð Rekurencja w której funkcja wywoÅ‚uje samÄ… siebie nazywamy bezpoÅ›redniÄ…
(ang. direct).
pð Czasem mamy do czynienia z rekurencja poÅ›rednia (ang. indirect) która
reprezentuje cykl o długości większej niż 1, np. (P, Q, R, P).
main
Graf wywołań dla algorytmu
sortowania przez scalanie
MakeList PrintList MergeSort
Rekurencja bezpośrednia
split merge
7 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Grafy nieskierowane
pð Czasem zasadne jest poÅ‚Ä…czenie wierzchoÅ‚ków krawÄ™dziami,
które nie posiadają zaznaczonego kierunku. Z formalnego
punktu widzenia taka krawędz
jest zbiorem dwóch
wierzchołków.
pð Zapis {u,v} mówi ze wierzchoÅ‚ki u oraz v sÄ… poÅ‚Ä…czone w dwóch
kierunkach. Jeśli {u,v} jest krawędzią nieskierowana, wierzchołki
u i v określa się jako sąsiednie (ang. adjacent) lub mianem
sąsiadów (ang. neighbors).
pð Graf zawierajÄ…cy krawÄ™dzie nieskierowane, czyli graf z relacjÄ…
symetryczności krawędzi, nosi nazwę grafu nieskierowanego
(ang. undirected graph).
8 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Grafy nieskierowane
Kahului
Graf nieskierowany reprezentujÄ…cy
22 60
drogi na wyspie Hawajów Maui.
Lahaina 16 Hana
10
Keokea
pð Droga to lista wierzchoÅ‚ków. Nieco trudniej jest sprecyzować co
to jest cykl, tak aby nie była to każda lista
(n1, n2, & , nk-1, nk, nk-1, & , n2, n1)
9 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Pewne pojęcia z teorii grafów
pð Teoria grafów jest dziedzinÄ… matematyki zajmujÄ…cÄ… siÄ™
właściwościami grafów.
pð Grafy peÅ‚ne:
Nieskierowany graf posiadający krawędzie pomiędzy każdą parą różnych
wierzchołków nosi nazwę grafu pełnego (ang. complete graph). Graf pełny o
n wierzchołkach oznacza się przez Kn.
Liczba krawędzi w nieskierowanym grafie Kn wynosi n(n-1)/2, w
skierowanym grafie Kn wynosi n2.
n1
n1 n1 n2 n1
n1
n2 n2 n3 n3 n4 n2 n3
K1 K2 K3 K4 K3
10 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Grafy planarne i nieplanarne
pð O grafie nieskierowanym mówi siÄ™ że jest planarny (ang. planar) wówczas,
gdy istnieje możliwość rozmieszczenia jego wierzchołków na płaszczyz
nie, a
następnie narysowania jego krawędzi jako lini ciągłych które się nie przecinają.
pð Grafy nieplanarne (ang. nonplanar) to takie które nie posiadajÄ… reprezentacji
płaskiej.
Reprezentacja planarna: Najprostsze grafy nieplanarne:
n1 n2
n1
n1 n2
n2 n3
n3 n4
n3 n4
n4 n5
K4
n5 n6
K5 K3,3
11 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Zastosowania planarności i kolorowanie grafów
pð Planarność ma duże zastosowanie do graficznych reprezentacji w informatyce
dla projektowania różnego rodzaju układów (np. scalonych, bramek, etc.)
pð Kolorowanie grafu (ang. graph coloring) polega na przypisaniu do każdego
wierzchołka pewnego koloru, tak aby żadne dwa wierzchołki połączone
krawędzią nie miały tego samego koloru.
pð Minimalna liczba kolorów potrzebna do takiej operacji nazwana jest liczbÄ…
chromatycznÄ… grafu (ang. chromatic number), oznaczanÄ… c(G).
Jeżeli graf jest pełny to jego liczba chromatyczna jest równą liczbie wierzchołków
Jeżeli graf możemy pokolorować przy pomocy dwóch kolorów to nazywamy go
dwudzielnym (ang. bipartite graph). Np. K3,3.
n1 n2
c(G)=4 n1
c(G)=2
n2 n3
n3 n4
n6
n4 n5
n5 n6
12 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Sposoby implementacji grafów
pð IstniejÄ… dwie standardowe metody reprezentacji grafów.
Pierwsza z nich, listy sąsiedztwa (ang. adjacency lists), jest, ogólnie rzecz biorąc, podobna do
implementacji relacji binarnych.
Druga, macierze sąsiedztwa (ang. adjacency matrices), to nowy sposób reprezentowania relacji
binarnych, który jest bardziej odpowiedni dla relacji, w przypadku którym liczba istniejących
par stanowi znaczącą część całkowitej liczby par, jakie mogłyby teoretycznie istnieć w danej
dziedzinie.
pð WierzchoÅ‚ki sÄ… ponumerowane kolejnymi liczbami caÅ‚kowitymi 0,1,....., MAX-1 lub
oznaczone za pomocą innego adekwatnego typu wyliczeniowego (używamy poniżej
typu NODE jako synonimy typu wyliczeniowego).
pð Wówczas można skorzystać z podejÅ›cia opartego na wektorze wÅ‚asnym.
pð Element successors[u] zawiera wskaz
nik do listy jednokierunkowej wszystkich
bezpośrednich następników wierzchołka u. Następniki mogą występować w dowolnej
kolejności na liście jednokierunkowej.
typedef struct CELL *LIST;
struct CELL {
NODE nodeName;
Listy sÄ…siedztwa:
LIST next;
}
LIST successors[MAX]
13 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Reprezentacja grafu za pomocÄ… list sÄ…siedztwa
pðListy sÄ…siedztwa zostaÅ‚y posortowane wg. kolejnoÅ›ci,
ale następniki mogą występować w dowolnej
kolejności na odpowiedniej liście sąsiedztwa.
0 1 2
0
0 1
1
3
2 3
2
0 1 4
4
2 4
3
1
4
14 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Reprezentacja grafu za pomocÄ… macierzy sÄ…siedztwa
pðTworzymy dwuwymiarowÄ… tablicÄ™;
BOOLEAN vertices[MAX][MAX];
w której element vertices[u][v] ma wartość TRUE
wówczas, gdy istnieje krawędz
(u, v), zaÅ› FALSE, w
przeciwnym przypadku.
0 1 2 3 4
0 1
0 1 1 1 0 0
1 0 0 0 1 0
2 3
2 1 1 0 0 1
3 0 0 1 0 1
4
4 0 1 0 0 0
15 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Porównanie macierzy sąsiedztwa z listami sąsiedztwa.
pð Macierze sÄ…siedztwa sÄ… preferowanym sposobem reprezentacji grafów wówczas, gdy
grafy są gęste (ang. dense), to znaczy, kiedy liczba krawędzi jest bliska maksymalnej
możliwej ich liczby.
pð Dla grafu skierowanego o n wierzchoÅ‚kach maksymalna liczba krawÄ™dzi wynosi n2.
pð JeÅ›li graf jest rzadki (ang. sparse) to reprezentacja oparta na listach sÄ…siedztwa może
pozwolić zaoszczędzić pamięć.
pð Istotne różnice miedzy przedstawionymi reprezentacjami grafów sÄ… widoczne już przy
wykonywaniu prostych operacji.
Preferowany sposób reprezentacji:
OPERACJA GRAF GESTY GRAF RZADKI
Wyszukiwanie krawędzi Macierz sąsiedztwa Obie
Znajdowanie następników Obie Lista sąsiedztwa
Znajdowanie poprzedników Macierz sąsiedztwa Obie
16 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Spójna składowa grafu nieskierowanego
pð Każdy graf nieskierowany można podzielić na jedna lub wiÄ™kszÄ…
liczbę spójnych składowych (ang. connected components).
pð Każda spójna skÅ‚adowa to taki zbiór wierzchoÅ‚ków, że dla
każdych dwóch z tych wierzchołków istnieje łącząca je ścieżka.
Jeżeli graf składa się z jednej spójnej składowej to mówimy że
jest spójny (ang. connected).
Kahului
22 60
To jest graf spójny
Lahaina 16 Hana
10
Keokea
17 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Spójne składowe jako klasy równoważności
pð PojÄ™cie spójnych skÅ‚adowych można potraktować formalnie jako klasy
równoważności relacji równoważności P zdefiniowanej na wierzchołkach
grafu nieskierowanego jako uPv wtedy i tylko wtedy, gdy istnieje droga z
wierzchołka u do v.
pð Sprawdzenie czy P jest relacjÄ… równoważnoÅ›ci
Relacja P jest zwrotna, to znaczy zachodzi uPu dla dowolnego wierzchołka u,
gdyż istnieje droga o długości 0 z dowolnego wierzchołka do niego samego.
Relacja P jest symetryczna. Jeśli zachodzi uPv, to istnieje droga z wierzchołka u
do v. Ponieważ graf jest nieskierowany, odwrotny porządek wierzchołków
również stanowi drogę. Stad zachodzi vPu.
Relacja P jest przechodnia. Załóżmy, ze relacje uPw oraz wPv są prawdziwe.
Wówczas istnieje pewna droga, na przykład (x1, x2, & , xj) z u do w. Zatem u=x1
oraz w=xj. Ponadto istnieje droga (y1, y2, & , yk) z wierzchołka w do v, gdzie
w=y1 oraz v=yk. Składając obie drogi razem otrzymujemy drogę z u do v, czyli
(u=x1, x2, & , xj= w= y1, y2, & , yk= v).
Relacja P dzieli graf na klasy równoważności. Każda klasa równoważności
zdefiniowana relacją drogi odpowiada spójnej składowej tego grafu.
18 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm wyznaczania spójnych składowych
pð Chcemy okreÅ›lić spójne skÅ‚adowe grafu G. Przeprowadzamy rozumowanie
indukcyjne.
pð Podstawa:
Graf Go zawiera jedynie wierzchołki grafu G i żadnej jego krawędzi. Każdy
wierzchołek stanowi odrębną spójną składową .
pð Indukcja:
Zakładamy, że znamy już spójne składowe grafu Gi po rozpatrzeniu pierwszych i
krawędzi, a obecnie rozpatrujemy (i+1) krawędz
{u, v}.
pð jeżeli wierzchoÅ‚ki u, v należą do jednej spójnej skÅ‚adowej to nic siÄ™ nie zmienia
pð jeżeli do dwóch różnych, to Å‚Ä…czymy te dwie spójne skÅ‚adowe w jednÄ….
x
v
u
y
19 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Struktura danych dla wyznaczania spójnych składowych
pð BiorÄ…c pod uwagÄ™ przedstawiony algorytm, musimy zapewnić szybkÄ…
wykonywalność następujących operacji:
1. gdy jest określony wierzchołek to znajdz
jego bieżącą spójną składową
2. połącz dwie spójne składowe w jedną
pð ZaskakujÄ…co dobre wyniki daje ustawienie wierzchoÅ‚ków każdej skÅ‚adowej w
strukturze drzewiastej, gdzie spójna składowa jest reprezentowana przez
korzeń.
aby wykonać operacje (1) należy przejść do korzenia
aby wykonać operacje (2) wystarczy korzeń jednej składowej określić jako
potomka korzenia składowej drugiej.
Przyjmijmy zasadę ze korzeń drzewa o mniejszej wysokości czynimy potomkiem.
pð Przy takiej konstrukcji czas wykonania instrukcji (1) jest O(log n), czas
wykonania instrukcji (2) jest O(1). Wyznaczenie wszystkich spójnych
składowych to O(m log n) gdzie m jest liczbą krawędzi a n liczbą
wierzchołków.
20 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Minimalne drzewa rozpinajÄ…ce
pð Drzewo rozpinajÄ…ce (ang. spanning tree) grafu nieskierowanego
G stanowi zbiór wierzchołków tego grafu wraz z podzbiorem
jego krawędzi, takich że:
łączą one wszystkie wierzchołki, czyli istnieje droga miedzy dwoma
dowolnymi wierzchołkami która składa się tylko z krawędzi drzewa
rozpinajÄ…cego.
tworzÄ… one drzewo nie posiadajÄ…ce korzenia, nieuporzÄ…dkowane. Oznacza
to że nie istnieją żadne (proste) cykle.
pð JeÅ›li graf G stanowi pojedynczÄ… spójnÄ… skÅ‚adowÄ… to drzewo
rozpinajÄ…ce zawsze istnieje. Minimalne drzewo rozpinajÄ…ce
(ang. minimal spanning tree) to drzewo rozpinające, w którym suma
etykiet jego krawędzi jest najmniejsza ze wszystkich możliwych
do utworzenia drzew rozpinajÄ…cych tego grafu.
21 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Minimalne drzewa rozpinajÄ…ce
A A
28 24 28
15
C B D C B D
11 11
12 12
20 20
13 13
E F E F
Graf nieskierowany Drzewo rozpinajÄ…ce
22 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Znajdowanie minimalnego drzewa rozpinajÄ…cego
pð Istnieje wiele algorytmów. Jeden z nich to algorytm Kruskala, który stanowi
proste rozszerzenie algorytmu znajdowania spójnych składowych. Wymagane
zmiany to:
należy rozpatrywać krawędzie w kolejności zgodnej z rosnącą wartością ich
etykiet,
należy dołączyć krawędz
do drzewa rozpinajÄ…cego tylko w takim wypadku gdy jej
końce należą do dwóch różnych spójnych składowych.
A A
24 24 (5)
28
15 (4)
15
C B D C B D
11 12 (2) 11 (1)
12
20
13 13 (3)
E F E F
Minimalne drzewo rozpinajÄ…ce
Graf nieskierowany
(w nawiasach podano kolejność dodawanych krawędzi)
23 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Znajdowanie minimalnego drzewa rozpinajÄ…cego
pð Algorytm Kruskala jest dobrym przykÅ‚adem algorytmu
zachłannego (ang. greedy algorithm), w przypadku którego
podejmowany jest szereg decyzji, z których każdą stanowi
wybranie opcji najlepszej w danym momencie. Lokalnie
podejmowane decyzje polegajÄ… w tym przypadku na wyborze
krawędzi dodawanej do formowanego drzewa rozpinającego.
pð Za każdym razem wybierana jest krawÄ™dz
o najmniejsze wartości
etykiety, która nie narusza definicji drzewa rozpinającego,
zabraniajÄ…cej utworzenia cyklu.
pð Dla algorytmu Kruskala można wykazać, ze jego rezultat jest
optymalny globalnie, to znaczy że daje on w wyniku drzewo
rozpinajÄ…ce o minimalnej wadze.
pð Czas wykonania algorytmu jest O(m log m) gdzie m to jest
większa z wartości liczby wierzchołków i liczby krawędzi.
24 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Uzasadnienie poprawności algorytmu Kruskala
pð Niech G bÄ™dzie nieskierowanym grafem spójnym.
(Dla niektórych etykiet dopuszczamy dodanie nieskończenie
malej wartości tak aby wszystkie etykiety były różne, graf G
będzie miał wobec tego unikatowe minimalne drzewo
rozpinające, które będzie jednym spośród minimalnych drzew
rozpinajÄ…cych grafu G o oryginalnych wagach).
pð Niech ciÄ…g e1, e2, & , em oznacza wszystkie krawÄ™dzie grafu G w
kolejności zgodnej z rosnącą wartością ich etykiet, rozpoczynając
od najmniejszej.
pð Niech K bÄ™dzie drzewem rozpinajÄ…cym grafu G o odpowiednio
zmodyfikowanych etykietach, utworzonym przez zastosowanie
algorytmu Kruskala, a T niech będzie unikatowym minimalnym
drzewem rozpinajÄ…cym grafu G.
25 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Uzasadnienie poprawności algorytmu Kruskala
pð Należy udowodnić ze K i T stanowiÄ… to samo drzewo. JeÅ›li sÄ…
różne musi istnieć co najmniej jedna krawędz
, która należy do
jednego z nich a nie należy do drugiego.
pð Niech ei oznacza pierwsza taka krawÄ™dz
spośród
uporządkowanych krawędzi, to znaczy każda z krawędzi e1, e2,
& , ei-1 albo należy do obu drzew K i T albo nie należy do
żadnego z nich.
pð IstniejÄ… dwa przypadki w zależnoÅ›ci czy krawÄ™dz
ei należy do
drzewa K czy do drzewa T. W każdym z tych przypadków
wykażemy sprzeczność, co będzie stanowić dowód, ze ei nie
może istnieć, a stąd że K=T, oraz że K stanowi minimalne
drzewo rozpinajÄ…ce grafu G.
26 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Uzasadnienie poprawności algorytmu Kruskala
pð Przypadek 1:
krawędz
ei należy do T, ale nie należy
do K.
Jeżeli algorytm Kruskala odrzuca ei,
oznacza to ze ei formuje cykl z pewna
droga P, utworzona z uprzednio
wybranych krawędzi drzewa K.
Jeżeli krawędzie drogi P należą to K to
ei
należą także do T.
A wiec P + ei utworzyłoby cykl w T co
Droga P (linia ciągła) należy
jest sprzeczne z definicja drzewa
zarówno do drzewa T jak i K,
rozpinającego. Stad niemożliwe jest aby
krawędz
ei należy tylko do T.
ei należała do T a nie należała do K.
27 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Uzasadnienie poprawności algorytmu Kruskala
pðPrzypadek 2:
krawędz
ei należy do K, ale nie należy do T.
Niech krawędz
ei łączy wierzchołki u i v.
Ponieważ drzewo T jest spójne, musi istnieć w
f w
T pewna acykliczna droga z wierzchołka u do
x
v. Niech nosi ona nazwę Q. Ponieważ w skład
Q nie wchodzi ei, Q + ei tworzy cykl prosty w
u
grafie G.
1. krawędz
ei posiada najwyższą wartość etykiety.
ei
v
Musiałoby to oznaczać ze K zawiera cykl co jest
niemożliwe.
Droga Q (linia ciągła)
2. na drodze Q istnieje krawędz
f która ma wartość
etykiety wyższą niż ei. Można by wiec usunąć f a
należy do drzewa T,
wprowadzić ei nie niszcząc spójności. A wiec
można dodać krawędz

rozpięte drzewo miałoby wartość mniejsza niż
ei i usunąć krawędz
f
wartość dla T co jest w sprzeczności z
poczÄ…tkowym twierdzeniem ze T jest minimalne.
28 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm przeszukiwania w głąb
pð Jest to podstawowa metoda badania grafów skierowanych.
pð Bardzo podobna do stosowanych dla drzew, w których startuje siÄ™ od
korzenia i rekurencyjnie bada wierzchołki potomne każdego odwiedzonego
wierzchołka.
pð Trudność polega na tym ze w grafie mogÄ… pojawiać siÄ™ cykle& Należy wobec
tego znaczyć wierzchołki już odwiedzone i nie wracać więcej do takich
wierzchołków.
pð Z uwagi na fakt, że w celu unikniÄ™cia dwukrotnego odwiedzenia tego samego
wierzchołka jest on odpowiednio oznaczany, graf w trakcie jego badania
zachowuje siÄ™ podobnie do drzewa.
pð W rzeczywistoÅ›ci można narysować drzewo, którego krawÄ™dzie rodzic-
potomek będą niektórymi krawędziami przeszukiwanego grafu G.
pð Takie drzewo nosi nazwÄ™ drzewa przeszukiwania w gÅ‚Ä…b (ang. depth-first-
search) dla danego grafu.
29 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm przeszukiwania w głąb
Las przeszukiwania:
dwa drzewa o korzeniach a, d
a
a
b d
b d
c f
e
c f
e
Jedno z możliwych
drzew
a
przeszukiwania
Graf skierowany
b d
c f
e
Las przeszukiwania w głąb.
30 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Drzewo przeszukiwania w głąb
6
a
5
krawędz

b d
4
wsteczna
c f
1 3
e
2
pðPo (podczas) konstruowaniu drzewa przeszukiwania w
głąb można ponumerować jego wierzchołki w
kolejności wstecznej (ang. post-order).
31 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Rekurencyjna funkcja przeszukiwania w głąb: void dfs
enum MARKTYPE {VISITED, UNVISITED}; typedef struct CELL *LIST;
typedef struct{ struct CELL {
enum MARKTYPE mark; NODE nodeName;
LIST successors; LIST next;
} GRAPH[MAX]; };
void dfs(NODE u, GRAPH G)
{
LIST p; /* lista sąsiedztwa dla wierzchołka u */
NODE v; /* wierzchołek w komórce wskazywanej przez p */
G[u].mark = VISITED;
p = G[u].successors;
while (p != NULL) {
v = p->nodeName;
if (G[y].mark == UNVISITED) dfs(v, G);
p = p->next;
}
}
32 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Znajdowanie cykli w grafie skierowanym
pð Podczas przeszukiwania w gÅ‚Ä…b grafu skierowanego G można
wszystkim wierzchołkom przypisać numery zgodne z kolejnością
wsteczną w czasie rzędu O(m).
pð KrawÄ™dzie wsteczne to takie dla których poczÄ…tki sÄ… równe lub
mniejsze końcom ze względu na numeracje wsteczną.
pð Zawsze gdy istnieje krawÄ™dz
wsteczna w grafie musi istnieć cykl.
pð Prawdziwe jest również twierdzenie odwrotne. Aby stwierdzić
czy w grafie występuje cykl należy przeprowadzić numerację
wsteczną a następnie sprawdzić wszystkie krawędzie.
pð CaÅ‚kowity czas wykonania testu cyklicznoÅ›ci to O(m), gdzie m
to większa z wartości liczby wierzchołków i liczby krawędzi.
33 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Sortowanie topologiczne
pð Załóżmy, że graf skierowany G jest acykliczny.
pð Dla każdego grafu możemy okreÅ›lić las poszukiwania w gÅ‚Ä…b,
określając numerację wsteczną jego wierzchołków.
pð Załóżmy, że (n1, n2, & , nk) okreÅ›la listÄ™ wierzchoÅ‚ków grafu G
w kolejności odwrotnej do numeracji wstecznej. To znaczy: n1
jest wierzchołkiem opatrzonym numerem n, n2 wierzchołkiem
opatrzonym numerem n-1 i ogólnie wierzchołek ni jest
opatrzony numerem n-i+1.
pð Kolejność wierzchoÅ‚ków na tej liÅ›cie ma ta wÅ‚asność, że
wszystkie krawędzie grafu G biegną od początku do końca, tzn.
poczÄ…tek poprzedza koniec.
34 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Sortowanie topologiczne
pð Takie uporzÄ…dkowanie nazywamy topologicznym (ang.
topological order), a proces znajdowania takiego uporzÄ…dkowania to
sortowanie topologiczne (ang. topological sorting).
pð Jedynie grafy acykliczne posiadajÄ… uporzÄ…dkowanie topologiczne.
pð WykonujÄ…c poszukiwanie w gÅ‚Ä…b możemy je okreÅ›lić w czasie
O(m).
pð Jedna z możliwoÅ›ci: odkÅ‚adać kolejno znalezione wierzchoÅ‚ki
 na stos . Po zakończeniu lista znajdująca się na stosie będzie
reprezentować uporządkowanie topologiczne grafu.
35 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Sortowanie topologiczne
UporzÄ…dkowanie topologiczne to (d,e,c,f,b,a)
1 2 4 6
d
a b c d
c e
3 5
f e
b f
a
Las przeszukiwania w głąb
Skierowany graf cykliczny
36 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Sortowanie topologiczne - zastosowania
pð UporzÄ…dkowanie topologiczne przydaje siÄ™ wówczas, gdy istniejÄ… pewne
ograniczenia odnośnie kolejności w jakiej mają być wykonywane zadania.
pð JeÅ›li krawÄ™dz
wiodącą od wierzchołka u do wierzchołka v jest rysowana
wówczas, gdy zadanie u musi zostać wykonane przed zadaniem v, to
uporządkowaniem zapewniającym wykonanie wszystkich żądań jest właśnie
uporzÄ…dkowanie topologiczne.
pð Podobny przykÅ‚ad to graf wywoÅ‚aÅ„ nierekurencyjnego zbioru funkcji, kiedy
należy przeanalizować każdą funkcje dopiero po dokonaniu analizy funkcji ją
wywołującej.
pð JeÅ›li krawÄ™dzie wiodÄ… od funkcji wywoÅ‚ujÄ…cych do wywoÅ‚ywanych, kolejność,
w której należy przeprowadzić takie analizy, to odwrócenie porządku
topologicznego, czyli uporzÄ…dkowanie wsteczne.
pð Zapewnia to że każda funkcja zostanie przeanalizowana dopiero po
dokonaniu analizy wszystkich innych wywoływanych przez nią funkcji.
37 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Sortowanie topologiczne - zastosowania
pðIstnienie cyklu w grafie reprezentujÄ…cym priorytety
zadań mówi o tym, że nie istnieje takie
uporządkowanie, dzięki któremu możliwe byłoby
wykonanie wszystkich zadań.
pðIstnienie cyklu w grafie wywoÅ‚aÅ„ pozwala stwierdzić
występowanie rekurencji.
38 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Problem osiągalności
pð Naturalne pytanie zwiÄ…zane z grafem skierowanym jest:
które wierzchołki są osiągalne z danego wierzchołka u przy założeniu, że
po grafie można się poruszać tylko zgodnie z kierunkiem krawędzi?
Taki zbiór wierzchołków określa się mianem zbioru osiągalności (ang.
reachable set) danego wierzchołka u.
pð Możemy wykorzystać rekurencyjnÄ… funkcje poszukiwania w gÅ‚Ä…b.
pð CaÅ‚kowity czas wykonania takiego zapytania to O(m n).
39 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Znajdowanie spójnych składowych
pð Do znajdowania spójnych skÅ‚adowych możemy użyć algorytmu
poszukiwania w głąb.
pð Traktujemy graf nieskierowany jako graf skierowany, w którym
każda krawędz
nieskierowana została zastąpiona dwiema
krawędziami skierowanymi wiodącymi w obu kierunkach.
pð Do reprezentacji grafu używamy list sÄ…siedztwa.
pð Tworzymy las przeszukiwania w gÅ‚Ä…b grafu skierowanego. Każde
drzewo w tym lesie odpowiada jednej składowej spójności grafu
nieskierowanego.
pð Czas wykonania algorytmu O(m) (przy użyciu struktury
drzewiastej, patrz poprzedni wykład, czas wykonania wynosi
O(m log n)).
40 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Dijkstry znajdowania najkrótszych dróg.
pðRozpatrujemy graf G (skierowany lub nieskierowany), w
którym wszystkie krawędzie zaetykietowano
wartościami reprezentującymi ich długości.
pðDÅ‚ugość (ang. distance) danej drogi stanowi wartość
sumy etykiet związanych z nią krawędzi. Minimalna
odległość z wierzchołka u do wierzchołka v to
minimalna długość którejś z dróg od u do v.
41 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Dijkstry znajdowania najkrótszych dróg.
pð Traktujemy wierzchoÅ‚ek s jako wierzchoÅ‚ek
z
ródłowy. W etapie pośrednim wykonywania
algorytmu w grafie G istnieją tzw. wierzchołki
ustalone (ang. settled), tzn. takie dla których
znane są odległości minimalne. W Graf G
szczególności zbiór takich wierzchołków
zawiera również wierzchołek s.
v
s
pð Dla nieustalonego wierzchoÅ‚ka v należy
droga
zapamiętać długość najkrótszej drogi
specjalna
specjalnej (ang. special path) czyli takiej która
rozpoczyna się w wierzchołku z
ródłowym,
wiedzie przez ustalone wierzchołki, i na
ostatnim etapie przechodzi z obszaru
ustalonego do wierzchołka v.
42 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Dijkstry znajdowania najkrótszych dróg.
pð Dla każdego wierzchoÅ‚ka u zapamiÄ™tujemy wartość dist(u).
pð JeÅ›li u jest wierzchoÅ‚kiem ustalonym, to dist(u) jest dÅ‚ugoÅ›ciÄ…
najkrótszej drogi ze z
ródła do wierzchołka u.
pð JeÅ›li u nie jest wierzchoÅ‚kiem ustalonym, to dist(u) jest
długością drogi specjalnej ze z
ródła do u.
pð Na czym polega ustalanie wierzchoÅ‚ków:
znajdujemy wierzchołek v który jest nieustalony ale posiada najmniejszą
dist(v) ze wszystkich wierzchołków nieustalonych
przyjmujemy wartość dist(v) za minimalną odległość z s do v
dostosowujemy wartości wszystkich dist(u) dla innych wierzchołków,
które nie są ustalone, wykorzystując fakt, że wierzchołek v jest już
ustalony.
Czyli porównujemy stare dist(u) z wartością dist(v)+etykieta(v, u) jeżeli
taka (v, u) krawędz
istnieje.
pð Czas wykonania algorytmu jest O(m log n).
43 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Dijkstry znajdowania najkrótszych dróg.
Etapy wykonania algorytmu Dijkstry
L
ETAPY ustalania wierzchołków
28 24
MIASTO (1) (2) (3) (4) (5)
H 0* 0* 0* 0* 0*
15
P 13 13 13* 13* 13*
M W K
M INF INF 33 33 33*
12
11
W INF INF 25 25* 25*
20
L INF 35 35 35 35
P H
K 11 11* 11* 11* 11* 13
44 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Indukcyjny dowód poprawności algorytmu
pð W celu wykazania poprawnoÅ›ci algorytmu Dijkstry
należy przyjąć, że etykiety krawędzi są nieujemne.
pð Indukcyjny dowód poprawnoÅ›ci wzglÄ™dem k
prowadzi do stwierdzenia że:
1. dla każdego wierzchołka ustalonego u, wartość dist(u) jest
minimalną odległością z s do u, a najkrótsza droga do u
składa się tylko z wierzchołków ustalonych.
2. dla każdego nieustalonego wierzchołka u, wartość dist(u)
jest minimalną długością drogi specjalnej z s do u (jeśli
droga nie istnieje wartość wynosi INF).
45 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Indukcyjny dowód poprawności algorytmu
pðPodstawa:
Dla k=1 wierzchołek s jest jedynym wierzchołkiem
ustalonym. Inicjalizujemy dist(s) wartością 0, co spełnia
warunek (1).
Dla każdego innego wierzchołka u, dist(u) jest
inicjalizowane wartością etykiety krawędzi (s, u), o ile taka
istnieje. Jeżeli nie istnieje, wartością inicjalizacji jest INF.
Zatem spełniony jest również warunek (2).
46 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Indukcyjny dowód poprawności algorytmu
pð Krok indukcyjny:
Załóżmy, ze warunki (1) i (2) za spełnione po ustaleniu k wierzchołków oraz niech v
będzie (k+1) ustalonym wierzchołkiem.
Warunek (1) jest wciąż spełniony ponieważ dist(v) jest najmniejsza długością drogi z
s do v.
pð Załóżmy, że tak nie jest. MusiaÅ‚a by wiec istnieć hipotetyczna krótsza droga do v wiodÄ…ca
przez w i u. Jednakże wierzchołek v został obrany jako k+1 ustalony, co oznacza, ze w tym
momencie dist(u) nie może być mniejsze od dist(v), gdyż wówczas jako (k+1)
wierzchołek wybrany zostałby wierzchołek u.
pð Na podstawie warunku (2) hipotezy indukcyjnej wiadomo, ze dist(u) jest minimalna
długością drogi specjalnej wiodącej do u. Jednak droga z s przez w do u jest drogą
specjalną, tak więc jej długość równa jest co najmniej dist(u). Stąd domniemana krótsza
droga z s do v wiodąca przez w i u ma długość równą co najmniej dist(v), ponieważ
pierwsza jej część, - z s do u  ma dÅ‚ugość dist(u), a dist(u) Å‚ð dist(v). StÄ…d warunek (1)
jest spełniony dla k+1 wierzchołków.
Graf G
Hipotetyczna krótsza droga do v
v
s
wiodÄ…ca przez w i u. w
u
47 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Indukcyjny dowód poprawności algorytmu
pðKrok indukcyjny  ciÄ…g dalszy:
Teraz należy pokazać, że warunek (2) jest spełniony po dodaniu do wierzchołków
ustalonych wierzchołka v.
pðWez
my pod uwagę pewien wierzchołek u, który wciąż pozostaje nieustalony po dodaniu v do
wierzchołków ustalonych. W najkrótszej drodze specjalnej do u musi istnieć pewien
wierzchołek przedostatni. Wierzchołkiem tym może być zarówno v, jak i pewien inny
wierzchołek w.
pðPrzyjmijmy, że wierzchoÅ‚kiem przedostatnim jest v. DÅ‚ugość drogi z s przez v do u wynosi
dist(v) + wartość etykiety v ®ð u.
pðPrzyjmijmy, że wierzchoÅ‚kiem przedostatnim jest w. Na podstawie warunku (1) hipotezy
indukcyjnej można stwierdzić, że najkrótsza droga z s do w składa się jedynie z wierzchołków,
które zostały ustalone przed v, stąd wierzchołek v nie występuje w tej drodze.
pðA wiÄ™c dÅ‚ugość drogi specjalnej do u siÄ™ nie zmienia po dodaniu v do wierzchoÅ‚ków
ustalonych.
pðPonieważ w momencie ustalania wierzchoÅ‚ka v przeprowadzona jest operacja dostosowywania
dist(u), warunek (2) jest spełniony.
Graf G
Wierzchołki ustalone
Dwie możliwości określenia
v
przedostatniego wierzchołka
s
u
w
w drodze specjalnej do u.
48 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Floyda-Warshalla znajdowania najkrótszych dróg.
pð JeÅ›li potrzebne jest poznanie minimalnych odlegÅ‚oÅ›ci miedzy wszystkimi
parami wierzchołków w grafie o n wierzchołkach, które posiadają etykiety o
wartościach nieujemnych, można uruchomić algorytm Dijkstry dla każdego
z n wierzchołków jako wierzchołka z
ródłowego.
pð Czas wykonania algorytmu Dijsktry wynosi O(m log n ), gdzie m oznacza
większą wartość z liczby wierzchołków i liczby krawędzi. Znalezienie w ten
sposób minimalnych odległości miedzy wszystkimi parami wierzchołków
zajmuje czas rzędu O(m n log n).
pð JeÅ›li m jest bliskie swojej maksymalnej wartoÅ›ci m ð n2 to można skorzystać z
implementacji algorytmu Dijkstry który działa w czasie O(n2). Wykonanie go
n razy daje czas rzędu O(n3).
pð Istnieje inny algorytm znajdowania minimalnych odlegÅ‚oÅ›ci miedzy
wszystkimi parami wierzchołków, noszący nazwę algorytmu Floyda-
Warshalla.
pð Jego wykonanie zajmuje czas rzÄ™du O(n3). Operuje na macierzach sÄ…siedztwa
a nie listach sÄ…siedztwa i jest koncepcyjnie prostszy.
49 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Floyda-Warshalla znajdowania najkrótszych dróg.
pð Podstawa algorytmu jest dziaÅ‚anie polegajÄ…ce na rozpatrywaniu po kolei każdego
wierzchołka grafu jako elementu centralnego (ang. pivot).
pð Kiedy wierzchoÅ‚ek u jest elementem centralnym, staramy siÄ™ wykorzystać fakt, że u
jest wierzchołkiem pośrednim miedzy wszystkimi parami wierzchołków.
pð Dla każdej pary wierzchoÅ‚ków, na przykÅ‚ad v i w, jeÅ›li suma etykiet krawÄ™dzi (v, u)
oraz (u, w) (na rysunku d+e) , jest mniejsza od bieżąco rozpatrywanej etykiety f
krawędzi wiodącej od v do w, to wartość f jest zastępowana wartością d+e.
0 0
Node u, v, w;
for (v = 0; w < MAX; v++)
for (w=0; w < MAX; w++)
1 1
dist[v][w] = edge[v][w];
& &
u
for (u=0; u< MAX; u++)
d e
for (v=0; v< MAX; v++)
v w
for (w=0; wf
if( dist[v][u]+dist[u][w] < dist[v][w])
& &
dist[v][w] = dist [v][u] + dist [u][w];
n-1 n-1
edge[v][w]  etykieta krawędzi, wierzchołki numerowane
50 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Floyda-Warshalla - Przykład
Macierz edge, która odzwierciedla
początkową postać macierzy dist
0
28 24
0 1 2 3 4 5
15
0 0 24 INF INF INF 28
4 5 1
1 24 0 11 INF INF INF
2 INF 11 0 13 INF INF
12
11
20
3 INF INF 13 0 20 12
3 2
4 INF INF INF 20 0 15
13
5 28 INF INF 12 15 0
51 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Floyda-Warshalla - Przykład
Macierz dist, po użyciu wierzchołka
0 jako elementu centralnego
0
28 24
0 1 2 3 4 5
15
0 0 24 INF INF INF 28
4 5 1
1 24 0 11 INF INF 52
2 INF 11 0 13 INF INF
12
11
20
3 INF INF 13 0 20 12
3 2
4 INF INF INF 20 0 15
13
5 28 52 INF 12 15 0
52 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Floyda-Warshalla - Przykład
Macierz dist, po użyciu wierzchołka
1 jako elementu centralnego
0
28 24
0 1 2 3 4 5
15
0 0 24 35 INF INF 28
4 5 1
1 24 0 11 INF INF 52
2 35 11 0 13 INF 63
12
11
20
3 INF INF 13 0 20 12
3 2
4 INF INF INF 20 0 15
13
5 28 52 63 12 15 0
itd& itd&
53 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Algorytm Floyda-Warshalla - Przykład
Ostateczna postać macierzy dist.
0
28 24
0 1 2 3 4 5
15
0 0 24 35 40 43 28
4 5 1
1 24 0 11 24 44 52
2 35 11 0 13 33 25
12
11
20
3 40 24 13 0 20 12
3 2
4 43 44 33 20 0 15
13
5 28 36 25 12 15 0
54 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Uzasadnienie poprawności algorytmu Floyda-Warshalla
pð Na dowolnym etapie dziaÅ‚ania algorytmu Floyda-
Warshalla odległość z wierzchołka v do wierzchołka
w stanowi długość najkrótszej z tych dróg, które
wiodą jedynie przez wierzchołki użyte dotąd jako
elementy centralne.
numery wyższe od k
pð Ponieważ wszystkie wierzchoÅ‚ki zostajÄ… w koÅ„cu
numery niższe od k
użyte jako elementy centralne, elementy dist[v][w]
zawierają po zakończeniu działań minimalne
długości wszystkich możliwych dróg.
v
w
pð Definiujemy k-drogÄ™ z wierzchoÅ‚ka v do
wierzchołka w jako drogę z v do w taką, że żaden
jej wierzchołek pośredni nie ma numeru wyższego
k-droga
od k.
pð Należy zauważyć, że nie ma ograniczenia odnoÅ›nie
tego, że v lub w mają mieć wartość k lub mniejszą.
pð k=-1 oznacza że droga nie posiada wierzchoÅ‚ków
pośrednich.
55 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Dowód indukcyjny
pð Teza indukcyjna S(k):
jeżeli etykiety krawędzi maja wartości nieujemne, to po przebiegu k  pętli,
element dist[v][w] ma wartość najkrótszej k  drogi z v do w lub ma wartość
INF, jeżeli taka droga nie istnieje.
pð Podstawa:
Podstawą jest warunek k = -1. Krawędzie i drogi składające się z pojedynczego
wierzchołka są jedynymi (-1) drogami.
pð Krok indukcyjy
Załóżmy ze S(k) jest spełnione i rozważmy co się dzieje z elementami dist[v][w]
w czasie k+1 przebiegu pętli.
Załóżmy, że P jest najkrótszą (k+1)  drogą wiodąca z v do w. Mamy do
czynienia z dwoma przypadkami, w zależności czy droga P prowadzi przez
wierzchołek k+1 .
k-drogę P można rozbić
k-droga Q k-droga R
v k+1 w
na dwie k-drogi, Q oraz R.
56 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Dowód indukcyjny
pð Przypadek 1:
Jeżeli P jest k-drogą, to znaczy, kiedy P nie wiedzie przez wierzchołek
k+1, to na podstawie hipotezy indukcyjnej wartość elementu dist[v][w]
jest równa długości P po zakończeniu k-tej iteracji. Nie można zmienić
wartości dist[v][w] podczas przebiegu wykonywanego dla wierzchołka
k+1 traktowanego jako element centralny, gdyż nie istnieją żadne krótsze
(k+1)-drogi.
pð Przypadek 2:
Jeżeli P jest (k+1)- droga, można założyć, że P przechodzi przez
wierzchołek k+1 tylko raz, gdyż cykl nigdy nie może spowodować
zmniejszenia odległości (przy założeniu że wszystkie etykiety maja
wartości nieujemne).
Stąd droga P składa się z k-drogi Q, wiodącej od wierzchołka v do k+1,
oraz k-drogi R, wiodącej od wierzchołka k+1 do w. Na podstawie
hipotezy indukcyjnej wartości elementów dist[v][k+1] oraz
dist[k+1][w] będą długościami dróg odpowiednio, Q i R, po
zakończeniu k-tej iteracji.
57 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Dowód indukcyjny
pð Ostatecznie wnioskujemy, że w (k+1) przebiegu, wartoÅ›ciÄ…
elementu dist[v][w] staje się długość najkrótszej (k+1)-drogi dla
wszystkich wierzchołków v oraz w.
pð Jest to twierdzenie S(k+1), co oznacza koniec kroku
indukcyjnego.
pð Wez
my teraz, że k=n-1. Oznacza to, że wiemy iż po
zakończeniu wszystkich n przebiegów, wartość dist[v][w]
będzie minimalną odległością dowolnej (n-1)-drogi wiodącej z
wierzchołka v do w. Ponieważ każda droga jest (n-1) drogą, więc
dist[v][w] jest minimalną długością drogi wiodącej z
wierzchołka v do w.
58 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAiIS UJ  2011/2012
Podsumowanie informacji o algorytmach grafowych
PROBLEM ALGORYTM(Y) CZAS WYKONANIA
Minimalne drzewo rozpinajÄ…ce Algorytm Kruskala O(m log n)
Znajdowanie cykli Przeszukiwanie w głąb O(m)
Uporządkowanie topologiczne Przeszukiwanie w głąb O(m)
Osiągalność w przypadku Przeszukiwanie w głąb O(m)
pojedynczego z
ródła
Spójne składowe Przeszukiwanie w głąb O(m)
Najkrótsza droga Algorytm Dijskry O(m log n)
dla pojedyncz. z
ródła
Najkrótsza droga dla Algorytm Dijskry O(m n log n)
wszystkich par
Algorytm Floyda O(n3)
59 29.11.2011
Prof. dr hab. Elżbieta Richter-Wąs


Wyszukiwarka