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.