1
Grafy. Algorytmy grafowe
Podstawowe pojęcia
Grafem (
graph
) nazywamy uporządkowaną parę G=(V, E):
V = {v
1
, v
2
,..., v
n
} - zbiór wierzchołków (węzłów) (
nodes, vertices
),
E = {v
i
, v
i+1
), i=1,2,...n-1 - zbiór krawędzi (łuków) (
arcs
,
edges
),
E - relacja binarna w zbiorze V.
ASD
LJ
S
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ędź postaci (v, u)∈E jest
reprezentowana przez strzałkę skierowaną v→u. 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
).
2
Podstawowe pojęcia
ASD
LJ
S
Ścieżka (
path
) – ciąg wierzchołków połączonych krawędziami. Ścieżka w grafie
skierowanym stanowi listę wierzchołków (v
1
, v
2
,..., v
k
), taką, że istnieje krawędź
łącząca każdy wierzchołek z następnym tzn. v
i
→
v
i+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ędź (v, v) nazywamy pętlą (
loop
).
Podstawowe pojęcia
ASD
LJ
S
Wierzchołek incydentny z krawędzią – wierzchołek, z którego wychodzi lub, do
którego wchodzi krawędź.
Wierzchołki adiacentne – posiadające tą samą krawędź.
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.
3
Podstawowe pojęcia
ASD
LJ
S
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.
Reprezentacje grafów
ASD
LJ
S
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=(a
vu
) rozmiaru |V|×|V| taką, że:
a
vu
=
1
jeżeli (v,u)∈E
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.
4
Macierz sąsiedztwa
Graf skierowany.
ASD
LJ
S
1
7
5
4
2
6
3
1
2
3
4
5
6
7
1
0
0
0
1
1
0
1
2
0
0
1
0
0
1
1
3
1
0
0
0
0
0
0
4
0
0
0
0
0
0
1
5
0
0
0
0
0
0
1
6
1
0
0
0
0
0
0
7
0
0
0
0
0
0
0
A =
Graf G=(E,V)
Macierz sąsiedztwa
Graf nieskierowany.
ASD
LJ
S
1
7
5
4
2
6
3
1
2
3
4
5
6
7
1
0
0
1
1
1
1
1
2
0
0
1
0
0
1
1
3
1
1
0
0
0
0
0
4
1
0
0
0
0
0
1
5
1
0
0
0
0
0
1
6
1
1
0
0
0
0
0
7
1
1
0
1
1
0
0
A =
Graf G=(E,V)
5
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 wskaźnik 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 wskaźnik do głowy listy związanej z i-tym wierzchołkiem.
ASD
LJ
S
Listy sąsiedztwa
ASD
LJ
S
1
7
5
4
2
6
3
Graf G=(E,V)
H
4
5
7
/
1
2
3
4
5
6
7
3
7
6
/
1
/
7
/
7
/
1
/
Graf skierowany.
6
Listy sąsiedztwa
ASD
LJ
S
Graf nieskierowany.
Graf G=(E,V)
1
7
5
4
2
6
3
H
3
4
7
/
1
2
3
4
5
6
7
3
7
6
/
1
1
1
1
Listy sąsiedztwa grafu nieskierowanego
5
6
/
2
/
7
/
7
/
2
/
1
2
4
5
/
Listy sąsiedztwa
ASD
LJ
S
H
4
5
7
/
1
2
3
4
5
6
7
3
7
6
/
1
/
7
/
7
/
1
/
Tablicowa reprezentacja list sąsiedztwa.
A
H
1
1
2
5
3
9
4
11
5
13
6
15
7
1
4
2
5
3
7
4
0
5
3
6
7
7
6
8
0
9
1
10
0
11
7
12
0
13
7
14
0
15
1
16
0
Elementy listy związanej z wierzchołkiem v zajmują spójny
fragment tablicy A, pozycje o indeksach począwszy od A[H[v]].
7
Porównanie reprezentacji grafów
ASD
LJ
S
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
Przechodzenie grafu
Przechodzenie grafu oznacza jednokrotne odwiedzenie wszystkich jego węzłów w
określonej kolejności.
ASD
LJ
S
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.
8
Sposoby przechodzenia
Przykład (przechodzenie drzewa).
Przechodzenie „w głąb”
Przechodzenie „wszerz”
ASD
LJ
S
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.
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
9
Przechodzenie DFS
SEARCH DEPTH(A,V)
{
FOR i=1,2,...,n {
V[i]=0;
}
FOR i=1,2,...,n {
IF(V[i]==0)
VISIT (A,V,i);
}
}
VISIT (A,V,i)
{
V[i]=1;
FOR k= 1,2,...,n {
IF(A[i,k]≠0)
IF(V[k]==0)
VISIT (A,V,k);
}
}
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).
ASD
LJ
S
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.
10
Przechodzenie DFS
Graf nieskierowany i jego DFS-drzewo.
Krawędzie drzewiaste
Krawędzie tylne
ASD
LJ
S
1
5
2
6
3
4
7
Krawędzie przechodzenia DFS
1
2
4
3
5
6
7
Graf G=(E, V)
1
2
4
3
5
7
6
DFS-drzewo grafu G
Kolejność przechodzenia : <1, 2, 3, 4, 7, 5, 6>
Przechodzenie DFS
ASD
LJ
S
1
2
4
3
5
6
7
1
2
4
3
5
7
6
SEARCH DEPTH(A,V)
{
FOR i=1,2,...,n {
V[i]=0;
}
FOR i=1,2,...,n {
IF(V[i]==0)
VISIT (A,V,i);
}
}
VISIT (A,V,i)
{
V[i]=1;
FOR k= 1,2,...,n {
IF(A[i,k]≠0)
IF(V[k]==0)
VISIT (A,V,k);
}
}
11
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ędź (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.
ASD
LJ
S
Graf G=(E, V)
7
1
4
2
5
3
6
7
1
4
2
5
3
6
Krawędzie przechodzenia DFS
B - krawędź wsteczna
C - krawędź poprzeczna
B
1
2
7
5
4
3
6
DFS - las
B
C
C
C
C
12
Przechodzenie BFS
SEARCH BREADTH(A,V,s)
{
ENQUEUE (Q,s);
WHILE(NOT EMPTY(Q)){
←
←
←
← stan kolejki
i:= DEQUEUE(Q);
V[i]:=1;
FOR kaŜdego k∈V
IF(A[i,k]≠0)
IF(V[k]=0) {
V[k]:=1;
ENQUEUE(Q,k)
}
}
}
1
2
4
3
5
6
7
Stan kolejki
1
2
5
6
5
6
3
6
3
3
4
7
A[n,n] - macierz sąsiedztwa,
V[k]:=1 - jeżeli węzeł k został odwiedzony,
s
- węzeł startowy.
Przeszukiwanie grafu „wszerz”.
Kolejność przeszukiwanych wirzchołków wg
algorytmu SEARCH_BREADTH()
:
< 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
13
Zadanie znalezienia ścieżki w labiryncie
Znaleźć drogę prowadzącą od miejsca startowego oznaczonego literą s do mety
oznaczonej literą t.
ASD
LJ
S
14
S
5
3
8
6
7
2
1
10
9
4
13
11
12
t
Reprezentacja grafowa labiryntu
Układ labiryntu
Algorytm Dijkstry
Poszukiwania najkrótszych dróg w grafie z jednego źródła (E. Dijkstra, 1959r).
ASD
LJ
S
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ędź (z najkrótszej drogi), do której
naleŜy wierzchołek v;
IF (Y==V)
Realizacja jest rozwiązana;
14
Algorytm Dijkstry
Graf jest reprezentowany przez dwuwymiarową tablicę.
Używane są tablice touch i length, gdzie dla i=1,2,W,n.
ASD
LJ
S
touch[i]
=
indeks wierzchołka v należącego do zbioru Y, takiego że krawędź
(v, v
i
) jest ostatnią krawędzią w bieżącej najkrótszej drodze z v
1
do v
i
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 n≥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.
Algorytm Dijkstry
ASD
LJ
S
Określić najkrótsze drogi z
wierzchołka v
1
1. Zostaje wybrany wierzchołek v
5
,
ponieważ jest najbliżej wierzchołka v
1
15
Algorytm Dijkstry
ASD
LJ
S
2. Zostaje wybrany wierzchołek v
4
,
ponieważ wiedzie do niego
najkrótsza droga z wierzchołka v.
Droga ta zawiera tylko te
wierzchołki pośrednie, które
należą do zbioru { v
5
}.
3. Zostaje wybrany wierzchołek v
3
ponieważ
wiedzie do niego najkrótsza droga z
wierzchołka v
1
. Droga ta zawiera tylko te
wierzchołki pośrednie, które należą do
zbioru { v
4
, v
5
}.
Algorytm Dijkstry
ASD
LJ
S
4. Najkrótsza droga z v
1
do v
2
to { v
1
v
5
v
4
v
2
}
Złożoność czasowa algorytmu Dijkstry T(n)=O(n
2
).
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.
ASD
LJ
S
Problem: określić minimalne drzewo rozpinające.
Dane wejściowe: wejściowe: liczba całkowita n≥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.
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ę.
ASD
LJ
S
b) Drzewo rozpinające
dla grafu G.
c) Minimalne drzewo
rozpinająe dla grafu G
a) Spójny, ważony, nieskierowany
graf G.
17
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.
ASD
LJ
S
F=∅;
WHILE (realizacja nie została rozwiązana)
1.
Wybierz krawędź zgodnie z pewnym warunkiem optymalnym
lokalnie; //procedura wyboru.
IF (dodanie krawędzi do F nie powoduje powstania cyklu)
Dodaj krawędź; //sprawdzenie wykonalności.
IF (T=(V,F) jest drzewem rozpinającym)
Realizacja jest rozwiązana; //sprawdzenie rozwiązania.
Algorytm Prima
Graf ważony będzie reprezentowny w postaci macierzy przyległości. Będzie to
tablica W o wymiarach n×n, zawierająca wartości liczbowe, gdzie.
ASD
LJ
S
W
ij
=
waga
jeżeli istnieje krawędź (v
i
, v
j
)
0
jeżeli i=j
∞
jeżeli nie istnieje krawędź (v
i
, v
j
)
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
Tablica reprezentująca macierz W
18
Algorytm Prima
Tworzone są dwie tablice, nearest oraz distance, gdzie dla i = 2, ... N.
ASD
LJ
S
nearest[i]= indeks wierzchołka należącego do zbioru Y, najbliższego v
distance[i]= waga krawędzi łączącej wierzchołek v
i
z wierzchołkiem
indeksowanym przez nearest[i].
Określić minimalne drzewo
rozpinające
1. Wierzchołek v
1
jest wybierany
jako pierwszy
Algorytm Prima
ASD
LJ
S
2. Wierzchołek v
2
zostaje wybrany
dlatego, że jest najbliższy {v
1
}
3. Wierzchołek v
3
zostaje wybrany
Dlatego, że jest najbliższy {v
1
, v
2
}
19
Algorytm Prima
ASD
LJ
S
4. Wierzchołek v
5
zostaje wybrany
dlatego, że jest najbliższy {v
1
, v
2
, v
3
}.
5. Zostaje wybrany wierzchołek v
4
.
Złożonośc czasowa algorytmu Prima T(n)=O(n
2
).