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

).