3938


Algorytmye grafowe

1. Definicje

Graf G=(V,E) składa się ze skończonego niepustych zbiorów wierzchołków V oraz krawędzi E. Graf jest zorientowany jeżeli krawędzie są parami uprządkowanymi wierzchołków (v,w), gdzie v jest końcem, a w początkiem krawędzi. Jeżeli krawędzie są parami nieuporządkowa-nymi różnych wierzchołków, graf jest niezorientowany.

|V|=N |E|=M

Dla pary wierzchołków (v,w) , mówi się że v sąsiaduje z w, krawędź prowadzi z v do w. Liczba wierzchołków sąsiadujących z v nazywana jest stopniem wyjściowym wierzchołka v

W grafie niezorientowanym

(v,w)=(w,v) , (w,v) jest także krawędzią grafu , w sąsiaduje z v.

Liczba wierzchołków sąsiadujących z v nazywana jest stopniem wierzchołka v.

Drogą w grafie jest ciąg krawędzi postaci

(v1,v2), (v2,v3),..... (vn-1,vn) . Droga prowadzi z v1 do vn i ma długość n-1.

Droga może być reprezentowana przez wierzchołki na tej drodze:

v1,v2,...vn

Jeden wierzchołek jest drogą o długosci 0.

Droga jest prosta, jeżeli wierzchołki i krawędzie są różne. Cykl jest drogą, która zaczyna się i kończy w tym samym wierzchołku. W grafie niezorientowanym minimalna długość cyklu wynosi 3. Graf bez cykli jest nazywany acyklicznym. Graf jest spójny, jeżeli istnieje droga pomiędzy każdą parą jego węzłów .

2. Reprezentacje grafu:

2.1. Macierz incydencji

Macierz incydencji w teorii grafów

TYPE TMatrix=ARRAY[1..N,1..M] OF -1..1;

zawiera -1 w wierszu odpowiadającym końcowi krawędzi

1 w wierszu odpowiadającym początkowi krawędzi

0 w pozostałych wierszach

dla grafu zorientowanego

Zajętość pamięci N*M

Macierz incydencji

(1,2) (1,3) (1,5) (2,4) (3,5) (4,5)

1 -1 -1 -1 0 0 0

2 1 0 0 -1 0 0

3 0 1 0 0 -1 0

4 0 0 0 1 0 -1

5 0 0 1 0 1 1

oraz 1 w wierszach odpowiadających pierwszemu i drugiemu wierzchołkowi krawędzi

0 w pozostałych wierszach

dla grafu niezorientowanego

(1,2) (1,3) (1,5) (2,4) (3,5) (4,5)

1 1 1 1 0 0 0

2 1 0 0 1 0 0

3 0 1 0 0 1 0

4 0 0 0 1 0 1

5 0 0 1 0 1 1

Duży czas potrzebny dla stwierdzenia istnienia krawędzi lub do jakich wierzchołków prowadzą krawędzie z wierzchołka x - przeszukiwanie wszystkich kolumn

2.2. Macierz sąsiedztwa wierzchołków

TYPE TGraf= ARRAY[1..N,1..N] OF 0..1;

VAR Graf:TGraf;

Graf[i,j]=1, jeżeli w grafie występuje krawędź łącząca wierzchołki v[i] i v[j].

Macierz sąsiedztwa dla grafu zorientowanego

N 1 2 3 4 5

1 0 1 1 0 1

2 0 0 0 1 0

3 0 0 0 0 1

4 0 0 0 0 1

5 0 0 0 0 0

Macierz sąsiedztwa dla grafu niezorientowanego

N 1 2 3 4 5

1 0 1 1 0 1

2 1 0 0 1 0

3 1 0 0 0 1

4 0 1 0 0 1

5 1 0 1 1 0

Dla grafu niezorientowanego jeżeli Graf[i,j]=1 to także Graf[j,i]=1

Reprezentacja przydatna w algorytmach często sprawdzających istnienie krawędzi w grafie. Czas wyszukania O(1).

Zajętość pamięci N*N, nawet dla O(N)krawędzi.

Duża liczba kroków O(N2) jest potrzebna do stwierdzenia czy graf posiada określoną cechę np czy jest acykliczny.

2.3. Macierz sąsiedztwa w postaci wektorów bitów. Mniejsza zajętość pamięci, większy czas dostępu wymagający wybrania odpowiedniego bitu z odpowiedniego bajtu.

2.4. Listy krawędzi

Przechowuje się pary numerów wierzchołków dla każdej krawędzi grafu uporządkowane leksykograficznie według numeracji węzłów. Zajętość pamięci 2*M. Wadą jest duża liczba kroków O(M) potrzebna do uzyskania zbioru wierzchołków do którego prowadzą krawędzie z danego wierzchołka. Można zastosować przeszukiwanie połówkowe.

1,2

1,3

1,5

2,4

3,5

4,5

2.5. Lista sąsiedztwa (lista incydencji adjacency list) wierzchołków sąsiadujących z wierzchołkiem v[i] dla każdego i=1..N, w reprezentacji list dynamicznych lub reprezentacji tablicowej.

PWezeł=^TWezel; [Aho]

TWezel=RECORD

numer:INTEGER;

nast,

pop:PWezel;

END;

TGraf=ARRAY[1..N] OF PWezeł;

[Banachowski,Kreczmar]

PElement=^TElement;

PWezel=^TWezel;

Element=RECORD

wierzcholek:PWezel;

nast:PElement;

END;

TWezel=RECORD

stary:BOOLEAN;

nast:PElement;

dn:INTEGER;

END;

VAR Graf:ARRAY[1..N] OF PWezel;

i,j:INTEGER;

Dla grafu niezorientowanego każda krawędź jest reprezentowana dwukrotnie. Liczba miejsc pamięci jest rzędu N+M.

Lista incydencji dla grafu zorientowanego

1 2 3 5

2 4

3 5

4 5

5

Lista incydencji dla grafu niezorientowanego

1 2 3 5

2 1 4

3 1 5

4 2 5

5 1 3 4

3. Algorytm przeglądania grafu metodą w głąb(depth first search).

Wartość początkowa pola stary=FALSE

po dojściu do węzła old=TRUE

dn numeruje wierzchołki grafu, wskazując kolejność odwiedzania wierzchołków grafu.

Przeglądanie rozpoczyna się od pewnego wierzchołka początkowego, który zostaje oznaczony jako przeglądany. Jako kolejny przeglądany jest jeden z wierzchołków sąsiadujących z wierzchołkiem przeglądanym, jeszcze nie odwiedzony. Po wyczerpaniu wierzchołków sąsiadujących nieodwiedzonych, cofa się do wierzchołka poprzedzającego wierzchołek odwiedzany i kontynuuje przechodzenie od następnego sąsiadującego z nim, jeszcze nie odwiedzonego wierzchołka grafu.

PROCEDURE Search(v:PWezel);

VAR w:PWezel;

k:PElement;

BEGIN

v^.stary:=TRUE;

v^.dn:=i;

WRITELN(`Odwiedzony wierzcholek `,i);

i:=i+1;

k:=v^.nast;

WHILE k<>NIL DO

BEGIN

w:=k^.wierzcholek;

IF NOT w^.stary

THEN search(w);

k:=k^.nast;

END;

END;

BEGIN

FOR i:=1 TO N DO

GRAF[i]^.stary:=FALSE;

i:=1;

FOR j:=1 TO N DO

IF NOT Graf[j]^.stary

THEN Search(Graf[j);

END;

koszt działania :

liczba krawędzi: M>=N

liczba wywołań search co najwyżej=N

przechodzenie po każdej krawędzi 1 raz

O(max(M,N))

Kolejność przeglądania wierzchołków grafu niezorientowanego

1 2 4 5 3

Wersja nierekurencyjna algorytmu omówiona w [Lipski]

4. Algorytm przeglądania grafu metodą wszerz (breadth first search)

Przy przeglądaniu wszerz najpierw odwiedza się kolejno wierzchołki do których prowadzą krawędzie z danego węzła, a następnie kolejno wierzchołki następnego poziomu. Algorytm wykorzystuje kolejkę do wpisywania wierzchołków sąsiadujących z wierzchołkiem odwiedzanym.

PROCEDURE Ws(v);

VAR

Kolejka,P:PWezel;

E:PElement;

BEGIN

Kolejka:=NIL;

Dolacz(Kolejka,v);

v^.stary:=TRUE;

WHILE NOT PustaKolejka(Kolejka) DO

BEGIN

P:= Pobierz(Kolejka);

Odwiedz(P);

E:=P^.Nast;

WHILE E<> NIL DO

IF NOT E^.wierzcholek^.stary

THEN

BEGIN

Wstaw(Kolejka,E^.wierzcholek);

E^.wierzcholek^.stary :=TRUE;

E:=E^.nast;

END;

END;

END;

Kolejność odwiedzania wierzchołków grafu: 1 2 3 5 4

Złożoność obliczeniowa O(N+M), gdyż każdy wierzchołek jest wstawiany do kolejki i usuwany z niej tylko 1 raz. Pętla przeglądania list incydencji wykonywana jest dla każdej krawędzi.

5. Znajdowanie drogi pomiędzy dwoma węzłami

Obydwa algorytymy przeglądania mogą być wykorzystane do znalezienia drogi pomiędzy dwoma wybranymi węzłami v i u. Wystarczy rozpocząć przeglądanie od wierzchołka v i zakończyć po odwiedzeniu wierzchołka u. Odwiedzone zostaną tylko te wierzchołki do których istnieje droga z wierzchołka początkowego.

W niektórych algorytmach uwzględnia się koszt krawędzi reprezentujący np. długość czyli odległość pomiędzy dwoma sąsiadującymi wierzchołkami w grafie. W tablicy incydencji można wówczas przechowywać wartość odpowiadającą długości krawędzi. Koszt krawędzi jest nazywany wagą krawędzi,

4. Algorytm minimalnego drzewa rozpinającego

Algorytm Kruskala znajdowania drzewa o minimalnym koszcie rozpiętego na danym grafie (niezorientowanym). Drzewo łączy wszystkie węzły drogą o minimalnym koszcie. Każda krawędź d należąca do E, ma określony koszt krawędzi c(d). Funkcja c jest funkcją kosztu krawędzi. Wykorzystywany np. do określania tras kolejowych pomiędzy zbiorem miast, tras wodociągów łączących przewidywane punkty odbioru.

Algorytm jest przykładem algorytmu zachłannego, ponieważ w każdym kroku wybiera najkrótszą krawędź. Każde drzewo o N węzłąch ma N-1 krawędzi.

Wykorzystuje: T- zbiór krawędzi budowanego drzewa,

F- zbiór krawędzi grafu, które nie zostały jeszcze rozważone,

U -podział zbioru wierzchołków V taki że trójka {V,U,T) jest lasem drzew.

Wartości początkowe:

T=[]

F={(2,3), (4,6), (3,4), (3,6), (3,5), (5,7), (2,5), (1,3), (1,4), (5,6),(1,2)}

3 4 4 5 6 7 7 7 8 9 10

U={{1}, {2}, {3}, {4}, {5}, {6}, {7}}

Algorytm pobiera ze zbioru F, krawędzie począwszy od krawędzi o minimalnym koszcie do krawędzi o koszcie maksymalnym.Dodaje do zbioru U wierzchołki kolejnej krawędzi, jeżeli jeszcze nie należą do żadnego podzbioru U

v w nowa krawędź U

2 3 (2,3) {1}, {2,3}, {4}, {5}, {6}, {7}}

4 6 (4,6) {1}, {2,3}, {4,6}, {5}, {7}}

3 4 (3,4) {1}, {2,3,4,6}, {5}, {7}}

3 6 - {1}, {2,3,4,6}, {5}, {7}}

3 5 (3,5) {1}, {2,3,4,5,6}, {7}}

5 7 (5,7) {1}, {2,3,4,5,6,7}}

2 5 - {1}, {2,3,4,5,6,7}}

1 3 (1,3) {1,2,3,4,5,6,7}}

1 4 - {1,2,3,4,5,6,7}}

5 6 - {1,2,3,4,5,6,7}}

1 2 - {1,2,3,4,5,6,7}}

Schemat algorytmu:

BEGIN

Inicjuj(T);

Inicjuj(F);

Inicjuj(U);

WHILE F<>[ ]DO

BEGIN

UsunMin(F,v,w);

Wybierz(U,A,v); {A zbior z U zawierający v}

Wybierz(U,B,w); {B zbior z U zawierający w}

IF A<>B

THEN

BEGIN

UNION(A,B); {polacz zbiory A i B}

Wstaw(v,w,T);

END;

END

END;

W wyniku uzyskuje się drzewo o minimalnym koszcie, łączące krawędzie wybrane:

6. Algorytm znajdywania najkrótszej drogi pomiędzy dwoma węzłami.

Wyznaczanie najkrótszych dróg w grafie dotyczy grafów zorientowanych o krawędziach z wagami. Najkrótsza droga jest drogą elementarną tzn każdy węzeł występuje w niej jeden raz.

Zastosowanie np. do wyznaczania najkrótszego połączenia pomiędzy dwoma miastami.

Wykorzystanie algorytmu zachłannego, który dla każdego węzła na drodze pomiędzy węzłami v i u,będzie wybierał najkrótszą krawędź wychodzącą z odwiedzanego węzła i prowadzącą do jeszcze nie odwiedzonego węzła, wyznaczy drogę pomiędzy dwoma wybranymi węzłami, ale niekoniecznie najkrótszą.

L(A)=min(5+L(C), 14+L(G), 3+L(D))

L(D)=min(7+L(E), 6+L(G), 11+L(C))=min(7+5, 6+6, 11+8)=

L(C)=min(2+L(F), 3+L(E))=min(7+5, 3+5)=8

L(G)=6

L(F)=7

L(E)=5

L

7. Inne algorytmy grafowe

Znajdowanie zbioru cykli w grafie

Znajdowanie składowych dwuspójnych.

Wyznaczanie drogi Eulera w której przez każdą krawędź grafu przechodzi się jeden raz. Droga taka isnieje, jeżeli w grafie wszystkie węzły oprócz jednego są stopnia parzystego.

Wyznaczanie drogi Hamiltona, w której przez każdy węzeł przechodzi się dokładnie 1 raz.

Znajdowanie odległości od węzła wybranego do wszystkich pozostałych węzłów w grafie.



Wyszukiwarka

Podobne podstrony:
3938
3938
3938
3938
3938
3938
3938
3938
020 2id 3938
3938
3938
3938
3938
3938

więcej podobnych podstron