Grafy. Algorytmy grafowe
Podstawowe pojęcia
Grafem (graph) nazywamy uporządkowaną parę G=(V, E):
V = {v1, v2,..., vn} - zbiór wierzchołków (węzłów) (nodes, vertices),
E = {vi, vi+1), i=1,2,...n-1 - zbiór krawędzi (łuków) (arcs, edges),
E - relacja binarna w zbiorze V.
Grafy dzielą się na dwie podstawowe grupy:
1. Grafy nieskierowane, niezorientowane (undirected graphs) - grafy, których
krawędzie są dwuelementowymi podzbiorami zbioru wierzchołków. Istotą grafu
nieskierowanego jest to, że nie istnieje kierunek krawędzi, {u,v}={v,u}, u`"v, u,v"V.
2. Grafy skierowane (zorientowane) (directed graphs) - grafy, których krawędzie są
uporządkowanymi parami wierzchołków. Każda krawędz postaci (v, u)"E jest
reprezentowana przez strzałkę skierowaną vu. Zapis (v,u), v,u"V oznacza, że
v jest początkiem (head), a u końcem krawędzi (tail). Wierzchołek v jest
poprzednikiem (predecessor) u, a wierzchołek u jest następnikiem (successor)
wierzchołka v. Wierzchołki v, u (niekoniecznie rożne) określa się jako sąsiednie
(adjacent) lub mianem sąsiadów (neighbors).
ASD LJ S
1
Podstawowe pojęcia
Ścieżka (path) ciąg wierzchołków połączonych krawędziami. Ścieżka w grafie
skierowanym stanowi listę wierzchołków (v1, v2,..., vk), taką, że istnieje krawędz
łącząca każdy wierzchołek z następnym tzn. vi vi+1 dla i=1,2,...,k-1.
Długość ścieżki (length) liczba krawędzi na ścieżce.
Odległość wierzchołków długość najkrótszej ścieżki łączącej wierzchołki.
Ścieżka prosta ścieżka, na której wierzchołki nie powtarzają się.
Cykl (cycle) ścieżka, której początek (pierwszy wierzchołek) jest równy końcowi
(ostatniemu wierzchołkowi. Ścieżka ta dla grafów skierowanych ma długość
większą lub równą 1, a dla grafów nieskierowanych ma wszystkie wierzchołki
poza skrajnymi parami rożne i długość większą lub równą 2.
Krawędz (v, v) nazywamy pętlą (loop).
ASD LJ S
Podstawowe pojęcia
Wierzchołek incydentny z krawędzią wierzchołek, z którego wychodzi lub, do
którego wchodzi krawędz.
Wierzchołki adiacentne posiadające tą samą krawędz.
Krawędzie adiacentne posiadające wspólny wierzchołek.
Wierzchołki spójne istnieje ścieżka pomiędzy nimi.
Wierzchołek separowany nie należy do żadnej krawędzi.
ASD LJ S
2
Podstawowe pojęcia
Typy grafów:
1. Graf spójny (connected) graf, którego każda para wierzchołków jest połączona
ścieżką.
2. Graf acykliczny (acyclic) graf nie zawierający cykli.
Drzewo spójny acykliczny graf nieskierowany.
Las acykliczny graf nieskierowany.
ASD LJ S
Reprezentacje grafów
Macierz sąsiedztwa (adjacency matric). Złożoność pamięciowa O(|V|2) .
Listy sąsiedztwa (adjacency lists). Złożoność pamięciowa O(|V|+ |E|).
Macierz sąsiedztwa jest macierzą kwadratową A=(avu) rozmiaru |V||V| taką, że:
1 jeżeli (v,u)"E
avu =
0 w przeciwnym przypadku
Macierz sąsiedztwa jest tablicą elementów 0 i 1. Elementami macierzy mogą być
również etykiety poszczególnych krawędzi.
ASD LJ S
3
Macierz sąsiedztwa
Graf skierowany.
1 2 3 4 5 6 7
1
1 0 0 0 1 1 0 1
2 0 0 1 0 0 1 1
3 1 0 0 0 0 0 0
A =
3 6
4 0 0 0 0 0 0 1
4 5
7 5 0 0 0 0 0 0 1
6 1 0 0 0 0 0 0
7 0 0 0 0 0 0 0
2
Graf G=(E,V)
ASD LJ S
Macierz sąsiedztwa
Graf nieskierowany.
1 2 3 4 5 6 7
1
1 0 0 1 1 1 1 1
2 0 0 1 0 0 1 1
3 1 1 0 0 0 0 0
3 6
A =
4 5
4 1 0 0 0 0 0 1
7
5 1 0 0 0 0 0 1
6 1 1 0 0 0 0 0
2
7 1 1 0 1 1 0 0
Graf G=(E,V)
ASD LJ S
4
Listy sąsiedztwa
Lista sąsiedztwa jest strukturą danych podającą dla każdego wierzchołka v"V
listę wierzchołków z nim sąsiadujących. Dla każdego wierzchołka tworzona jest
jedna lista.
Każdej krawędzi grafu odpowiada jeden węzeł listy, a każdemu wierzchołkowi
grafu odpowiada jeden wskaznik listy (który wskazuje początek listy).
Lista związana z danym wierzchołkiem v"V zawiera (w dowolnej kolejności)
wszystkie te wierzchołki u"V, dla których istnieją w grafie krawędzie (v, u).
Zestw takich list może być zaimplemntowany w postaci tablicy, której i-ty
element zawiera wskaznik do głowy listy związanej z i-tym wierzchołkiem.
ASD LJ S
Listy sąsiedztwa
Graf skierowany.
H
1
1 4 5 7 /
2
3 7 6 /
3
3 6
1 /
4 5
4
7
7 /
5
7 /
6
2
1 /
7
Graf G=(E,V)
ASD LJ S
5
Listy sąsiedztwa
Graf nieskierowany.
H
3 4 7 / 5 6 /
1
1
2
3 7 6 /
3 1 2 /
3 6
4
1 7 /
4 5
5
1 7 /
7
6 1 2 /
7
1 2 4 5 /
2
Listy sąsiedztwa grafu nieskierowanego
Graf G=(E,V)
ASD LJ S
Listy sąsiedztwa
A
Tablicowa reprezentacja list sąsiedztwa.
1 4
2 5
H
3 7
H
1 4 5 7 /
4 0
1 1
2
3 7 6 / 5 3
2 5
3
6 7
1 /
3 9
4
7 6
7 /
4 11
5 8 0
7 /
5 13
9 1
6
1 / 6 15
10 0
7
7
11 7
12 0
13 7
14 0
Elementy listy związanej z wierzchołkiem v zajmują spójny
fragment tablicy A, pozycje o indeksach począwszy od A[H[v]].
15 1
16 0
ASD LJ S
6
Porównanie reprezentacji grafów
Dla operacji dodawania i usuwania krawędzi najodpowiedniejsza jest
reprezentacja list sąsiedztwa.
Dla grafów rzadkich (sparse) reprezentacja na listach pozwoli zaoszczędzić
pamięć.
Macierze sąsiedztwa są preferowanym sposobem reprezentacji grafów
wówczas, gdy grafy są gęste (dense).
Operacja Graf gęsty Graf rzadki
Wyszukiwanie krawędzi Macierz sąsiedztwa Obie reprezentacje
Znajdowanie następników Obie reprezentacje Lista sąsiedztwa
Znajdowanie poprzedników Macierz sąsiedztwa Obie reprezentacje
ASD LJ S
Przechodzenie grafu
Przechodzenie grafu oznacza jednokrotne odwiedzenie wszystkich jego węzłów w
określonej kolejności.
Strategie przechodzenia grafu:
Przechodzenie w głąb DFS (Depth First Search).
Przechodzenie wszerz BFS ( Breadth First Search).
Idea algorytmów przechodzenia grafu wg. DFS, BFS:
1. Wybrać wierzchołek początkowy.
2. Odwiedzić jego sąsiadów.
3. Odwiedzić kolejnych sąsiadów (według określonego sposobu tak, żeby nie
wracać do już odwiedzonych), aż do momentu kiedy nie ma już więcej
wierzchołków do odwiedzenia.
ASD LJ S
7
Sposoby przechodzenia
Algorytm przechodzenia w głąb maksymalnie eksploruje raz obraną ścieżkę przed
wybraniem następnej.
Algorytmu przechodzenia wszerz rozważa najpierw wszystkie węzły grafu o
jednakowej głębokości.
Przykład (przechodzenie drzewa).
Przechodzenie w głąb Przechodzenie wszerz
ASD LJ S
Przechodzenie DFS
Przechodzenie grafu wg. DFS (algorytm wysokopoziomowy):
DFS()
{
FOR ka\dego węzła v"V
IF (węzeł v nie jest oznaczony)
VISIT (v);
}
VISIT (v)
{
Oznaczyć v jako węzeł odwiedzony;
FOR ka\dego sąsiada u węzła v
IF (węzeł u nie jest oznaczony)
VISIT (u);
}
ASD LJ S
8
Przechodzenie DFS
SEARCH DEPTH(A,V) VISIT (A,V,i)
{ {
FOR i=1,2,...,n { V[i]=1;
V[i]=0; FOR k= 1,2,...,n {
} IF(A[i,k]`"0)
IF(V[k]==0)
FOR i=1,2,...,n {
VISIT (A,V,k);
IF(V[i]==0)
}
VISIT (A,V,i);
}
}
}
A[n,n] - macierz sąsiedztwa węzłów,
V [n] - tablica węzłów,
V[k]=1 - jeżeli węzeł k został odwiedzony.
ASD LJ S
Przechodzenie DFS
W wyniku przeszukiwania w głąb grafu nieskierowanego każda z jego
krawędzi zaliczona zostaje do jednej z dwóch kategorii:
1. Krawędzie drzewowe (tree arcs) - krawędzie (v,u) ), dla których wywołanie
VISIT() dla v skutkuje bezpośrednim wywołaniem VISIT() dla u lub
odwrotnie. (bezpośrednie wywołanie dotyczy wywołania na sąsiednich
poziomach rekurencji).
2. Krawedzie tylne (back arcs) krawędzie (v,u) takie, że żadne z wywołań
VISIT() dla v i u nie są bezpośrednie, lecz ma charakter pośredni (np.
VISIT(v) powoduje wywołanie VISIT(x), które powoduje wywołanie
VISIT(w) , wobc tego v staje się przodkiem u).
Krawędzie drzewowe, tworzą drzewo przechodzenia w głąb DFS-tree (depth-first
search tree). DFS-drzewa tworzą las rozpinający przechodzenia zstępującego
(depth first spanning forest) - DFS-las.
ASD LJ S
9
Przechodzenie DFS
Graf nieskierowany i jego DFS-drzewo.
1
1 2 3
2
4
3
5 7
6
4 5
Graf G=(E, V)
7 6
1 2 3
DFS-drzewo grafu G
4
Krawędzie drzewiaste
5 7
6
Krawędzie tylne
Krawędzie przechodzenia DFS
Kolejność przechodzenia : <1, 2, 3, 4, 7, 5, 6>
ASD LJ S
Przechodzenie DFS
SEARCH DEPTH(A,V)
1 2 3
{
FOR i=1,2,...,n {
4
V[i]=0;
}
5 7
6
FOR i=1,2,...,n {
IF(V[i]==0)
VISIT (A,V,i);
1
}
}
2
VISIT (A,V,i)
{
V[i]=1;
3
FOR k= 1,2,...,n {
IF(A[i,k]`"0)
IF(V[k]==0)
4 5
VISIT (A,V,k);
}
} 7 6
ASD LJ S
10
Przechodzenie DFS
Klasyfikacja krawędzi dla grafów zorientowanych:
1. Krawędzie drzewowe (tree arcs) - krawędzie tworzące las przechodzenia w
głąb. Krawędz (v, u ) jest krawędzią drzewową, jeśli wierzchołek u został
odwiedzony w wyniku zbadania krawędzi (v, u).
2. Krawędzie powrotne (back arcs) - krawędzie (v, u) łączące wierzchołek v z
jego przodkiem u w drzewie przechodzenia w głąb . Pętle są traktowane jako
krawędzie powrotne.
3. Krawędzie w przód (forward arcs) - krawędzie niedrzewowe (v, u), które łączą
wierzchołek v z jego potomkiem u w drzewie przechodzenia w głąb.
4. Krawędzie poprzeczne (cross arcs) - krawędzie łączące wierzchołki z tego
samego drzewa przechodzenia w głąb, jeżeli tylko jeden z wierzchołków nie
jest przodkiem drugiego, lub łączą wierzchołki z różnych drzew
przechodzenia w głąb.
ASD LJ S
Przechodzenie DFS
Graf skierowany i jego DFS-drzewo.
1 2 3
7
1
7 B
B
C
3 6
2
C
4 5 6
C
4
5
Graf G=(E, V)
C
DFS - las
1 2 3
B - krawędz wsteczna
7
C - krawędz poprzeczna
4 5 6
Krawędzie przechodzenia DFS
ASD LJ S
11
Przechodzenie BFS
Przeszukiwanie grafu wszerz .
1 2 3
SEARCH BREADTH(A,V,s)
{
4
ENQUEUE (Q,s);
WHILE(NOT EMPTY(Q)){
! stan kolejki
!
!
!
5 7
6
i:= DEQUEUE(Q);
V[i]:=1;
Stan kolejki
FOR ka\dego k"V
IF(A[i,k]`"0)
IF(V[k]=0) {
3
6
V[k]:=1;
ENQUEUE(Q,k)
5 6
3
}
1
2 5 3
6 4 7
}
}
A[n,n] - macierz sąsiedztwa,
Kolejność przeszukiwanych wirzchołków wg
V[k]:=1 - jeżeli węzeł k został odwiedzony,
algorytmu SEARCH_BREADTH():
s - węzeł startowy.
< 1, 2, 5, 6, 3, 4, 7 >
ASD LJ S
Zastosowania grafów
Przykłady zastosowania grafów.
Sortowanie topologiczne (topological ordering) - liniowe uporządkowanie węzłów
w skierowanym grafie acyklicznym. Zastosowanie: wyznaczenie kolejności
wykonywania zależnych zadań.
Kolorowanie grafów (graph coloring) - proces kolorowania węzłów tak, aby żadne
dwa połączenia ze sobą nie miały takiego samego koloru. Określenie minimalnej
liczby kolorów (liczba chromatyczna).
Problem cyklu Hamiltona (Hamiltonian path) - określenie optymalnej ścieżki
łączącej wszystkie węzły. Zagadnienie komiwojażera (Traveling Salesman Problem)
Problemy szeregowania zadań (scheduling problem, sequencing problem).
Osiągalność w grafie (Reachability problem).
Zagadnienie przepływu (Max-flow Problem).
Problem przydziału (Assignment problem ).
ASD LJ S
12
Zadanie znalezienia ścieżki w labiryncie
Znalezć drogę prowadzącą od miejsca startowego oznaczonego literą s do mety
oznaczonej literą t.
t
12
9
3
11
4 5
2 1 13
6 7
10
14
S 8
Reprezentacja grafowa labiryntu
Układ labiryntu
ASD LJ S
Algorytm Dijkstry
Poszukiwania najkrótszych dróg w grafie z jednego zródła (E. Dijkstra, 1959r).
Wysokopoziomowy algorytm (zachłanny, greedy approach).
Short Path
Y={v1);
F=";
WHILE (realizacja nie została rozwiązana)
1. Wybierz ze zbioru V-Y wierzchołek v, mający najkrótszą drogę do
v1, u\ywając jako wierzchołków pośrednich tylko tych, które
nale\ą do Y;
2. Dodaj nowy wierzchołek v do Y;
3. Dodaj do zbioru F nową krawędz (z najkrótszej drogi), do której
nale\y wierzchołek v;
IF (Y==V)
Realizacja jest rozwiązana;
ASD LJ S
13
Algorytm Dijkstry
Graf jest reprezentowany przez dwuwymiarową tablicę.
Używane są tablice touch i length, gdzie dla i=1,2, ,n.
touch[i] = indeks wierzchołka v należącego do zbioru Y, takiego że krawędz
(v, vi) jest ostatnią krawędzią w bieżącej najkrótszej drodze z v1 do vi
zawierającej jako wierzchołki pośrednie tylko te należące do zbioru Y.
length[i]= długość bieżącej najkrótszej drogi z v1 do vi, zawierającej jako
wierzchołki pośrednie tylko te należące do zbioru Y
Problem: określić najkrótsze drogi z wierzchołka v1 do wszystkich innych
wierzchołków w ważonym grafie skierowanym.
Dane wejściowe: liczba całkowita ne"2 oraz spójny, ważony graf skierowany,
zawierający n wierzchołków. Graf jest reprezentowany przez tablicę
dwuwymiarową W, której wiersze i kolumny są indeksowane od 1 do n,
gdzie element W[i,j] jest wagą krawędzi między wierzchołkiem i-tym a j-tym.
Dane wyjściowe: zbiór krawędzi F, zawierający krawędzie najkrótszych dróg.
ASD LJ S
Algorytm Dijkstry
Określić najkrótsze drogi z 1. Zostaje wybrany wierzchołek v5,
wierzchołka v1 ponieważ jest najbliżej wierzchołka v1
ASD LJ S
14
Algorytm Dijkstry
2. Zostaje wybrany wierzchołek v4,
3. Zostaje wybrany wierzchołek v3 ponieważ
ponieważ wiedzie do niego
wiedzie do niego najkrótsza droga z
najkrótsza droga z wierzchołka v.
wierzchołka v1. Droga ta zawiera tylko te
Droga ta zawiera tylko te
wierzchołki pośrednie, które należą do
wierzchołki pośrednie, które
zbioru { v4, v5}.
należą do zbioru { v5}.
ASD LJ S
Algorytm Dijkstry
4. Najkrótsza droga z v1 do v2
to { v1 v5 v4 v2}
Złożoność czasowa algorytmu Dijkstry T(n)=O(n2).
ASD LJ S
15
Minimalne drzewo rozpinające
Drzewo rozpinające (spanning tree) grafu G to spójny podgraf, który zawiera
wszystkie wierzchołki należące do G i jest drzewem.
Problem: określić minimalne drzewo rozpinające.
Dane wejściowe: wejściowe: liczba całkowita ne"2 oraz spójny, ważony graf
nieskierowany, zawierający n wierzchołków. Graf jest reprezentowany przez
tablicę dwuwymiarową W, której wiersze i kolumny są indeksowane od 1 do n,
gdzie element W jest wagą krawędzi między wierzchołkiem i-tym a j-tym.
Dane wyjściowe: Dane wyjściowe: zbiór krawędzi F w minimalnym drzewie
rozpinającym danego grafu.
ASD LJ S
Minimalne drzewo rozpinające
Drzewo rozpinające (spanning tree) grafu G to spójny podgraf, który zawiera wszystkie
wierzchołki należące do G i jest drzewem.
Spójny podgraf o minimalnej wadze musi być drzewem rozpinającym, nie każde
drzewo rozpinające ma minimalną wagę.
a) Spójny, ważony, nieskierowany b) Drzewo rozpinające
c) Minimalne drzewo
graf G. dla grafu G.
rozpinająe dla grafu G
ASD LJ S
16
Minimalne drzewo rozpinające
Drzewo rozpinające (spanning tree) grafu G to spójny podgraf, który zawiera
wszystkie wierzchołki należące do G i jest drzewem.
F=";
WHILE (realizacja nie została rozwiązana)
1. Wybierz krawędz zgodnie z pewnym warunkiem optymalnym
lokalnie; //procedura wyboru.
IF (dodanie krawędzi do F nie powoduje powstania cyklu)
Dodaj krawędz; //sprawdzenie wykonalności.
IF (T=(V,F) jest drzewem rozpinającym)
Realizacja jest rozwiązana; //sprawdzenie rozwiązania.
ASD LJ S
Algorytm Prima
Graf ważony będzie reprezentowny w postaci macierzy przyległości. Będzie to
tablica W o wymiarach nn, zawierająca wartości liczbowe, gdzie.
waga jeżeli istnieje krawędz (vi, vj)
Wij =
" jeżeli nie istnieje krawędz (vi, vj)
0 jeżeli i=j
Tablica reprezentująca macierz W
1 2 3 4 5
1 0 1 3 " "
2 1 0 3 6 "
3 3 3 0 4 2
4 " 6 4 0 5
5 " " 2 5 0
ASD LJ S
17
Algorytm Prima
Tworzone są dwie tablice, nearest oraz distance, gdzie dla i = 2, ... N.
nearest[i]= indeks wierzchołka należącego do zbioru Y, najbliższego v
distance[i]= waga krawędzi łączącej wierzchołek vi z wierzchołkiem
indeksowanym przez nearest[i].
1. Wierzchołek v1 jest wybierany
Określić minimalne drzewo
jako pierwszy
rozpinające
ASD LJ S
Algorytm Prima
2. Wierzchołek v2 zostaje wybrany 3. Wierzchołek v3 zostaje wybrany
dlatego, że jest najbliższy {v1} Dlatego, że jest najbliższy {v1, v2}
ASD LJ S
18
Algorytm Prima
4. Wierzchołek v5 zostaje wybrany
5. Zostaje wybrany wierzchołek v4.
dlatego, że jest najbliższy {v1, v2, v3}.
Złożonośc czasowa algorytmu Prima T(n)=O(n2).
ASD LJ S
19
Wyszukiwarka
Podobne podstrony:
nw asd w3nw asd w2nw asd w9nw asd w2nw asd w1nw asd w6nw asd w7nw asd w5nw asd w10nw asd w11ASD w8,w9nw asd w4więcej podobnych podstron