ALGORYTMY

GRAFOWE

PRZESZUKIWANIE W GŁĄB

{ "Odwiedza" każdy wierzchołek grafu G ;
Wierzchołki “odwiedzone” mają kolor czarny }

DFS-VISIT (u);
{"Odwiedza" wierzchołki
składowej spójności
zawierającej wierzchołek u }

begin
1. kolor (u) := SZARY;
2. for każdy v Adj (u) do

3. if kolor (v) = BIAŁY
4. then DFS-VISIT
(v);
5. kolor (u) := CZARNY;

end;

DFS (G);

begin

1. for każdy u  V(G) do

2. kolor (u) := BIAŁY;

3. for każdy u V(G) do

4. if kolor (u) = BIAŁY
5. then DFS-VISIT
(u);
end;

PRZESZUKIWANIE WSZERZ

BFS (G,s);

{Jeśli G jest spójny, to odwiedza każdy wierzchołek grafu G,
jeśli niespójny, to odwiedza każdy wierzchołek składowej
spójności zawierającej wierzchołek s .Wierzchołki “odwiedzone”
mają kolor czarny }

begin

1. for każdy uV(G)–{s}

do
2. kolor (u) := BIAŁY;

3. kolor (s) := SZARY;

4. Q := {s};

while Q <>  do

begin
1. u:= head (Q);
2. for każdy v  Adj (u) do

3. begin
4. if kolor (v) = BIAŁY
5. then begin
6. kolor (v) =
SZARY;

7.

ENQUEUE

(Q,v);

end;
end;

8. DEQUEUE (Q);
9. kolor (u) := CZARNY;
end end;

MST-KRUSKAL (G, w);

{

Wyznacza zbiór ET krawędzi minimalnego drzewa spinającego

spójnego grafu G

}

begin

ET := ;

for każdy v  V(G) do

MAKE – SET (v);

posortuj krawędzie z E(G)
niemalejąco względem wag w ;

for każda krawędź {u,v}  E(G)

(w kolejności niemalejących wag)
do

if FIND-SET (u) <> FIND-SET (v)
then
begin
ET := ET  {{u,v}};

UNION (u,v)
end ;

return ET
end ;

MST – PRIM (G, w, r );

{ Wyznacza zbiór krawędzi ET = { {v,



(v)}: v



V(G) – {r} }

minimalnego drzewa spinającego spójnego grafu G }

begin

Q := V(G);
for każdy u  Q do

key(u) := ;

key(r) := 0;
(r) := NIL;

while Q <>  do

begin
u := EXTRACT-MIN (Q);
for każdy v  Adj(u) do

if v  Q and w(u,v) < key(v)

then
begin
(v) := u;

key(v) := w(u,v)

end
end
end;

RELAX (u, v, w);

{ Może zmniejszyć wartość d(v) i zmienić



(v) }

begin

if d(v) > d(u) + w(u,v)
then
begin
d(v) := d(u) + w(u,v);
(v) := u

end
end;

4

9

7

4

3

3

u

v

u

v

DIJKSTRA (G, w, s);

{ Wyznacza odległość każdego wierzchołka grafu G od wierzchołka s }

begin
for każdy v  V(G) do

begin
d(v) := ;

(v) := NIL;

end;

d(s) := 0;

S := ;

Q := V(G);

while Q <>  do

begin

u := EXTRACT-MIN (Q);
S := S  {u};

for każdy v  Adj(u) do

RELAX (u, v, w);

end
end;

begin

for każdy v  V(G)

do
begin
d(v) := ;

(v) := NIL;

end;

d(s) := 0;

BELLMAN – FORD (G, w, s);

{ Testuje czy graf ma cykle ujemnej długości ;
jeśli nie ma, to znajduje odległość każdego wierzchołka grafu
G
od wierzchołka s }

for i := 1 to |V(G)| - 1 do
for każda krawędź {u,v}  E(G) do

RELAX (u, v, w);

for każda krawędź {u,v}  E(G) do

if d(v) > d(u) + w(u,v)
then return FALSE;

return TRUE

end;

begin
for każda krawędź
(u,v)E(G)

do
begin
f(u,v) := 0;
f(v,u) := 0
end;

while istnieje ścieżka P

st

w sieci residualnej G

f

do

begin
c

f

(P

st

) := min { c

f

(u,v) : (u,v) 

P

st

};

for każda krawędź (u,v)  P

st

do
begin
f(u,v) := f(u,v) + c

f

(P

st

);

f(v,u) :=  f(u,v);

end
end

end

FORD-FULKERSON (G,c,s,t) ;

{

Jeśli c przyjmuje wartości całkowite, to algorytm wyznacza

maksymalny przepływ z s do t w sieci (G,c,s,t ) }

begin
for każdy wierzchołek u
V(G)

do
begin
h(u) := 0;
e(u) := 0
end;
for każda krawędź (u,v) 

E(G)
do
begin
f(u,v) := 0;
f(v,u) := 0
end;
h(s) := V(G);

for każdy wierzchołek u  Adj

(s) do
begin
f(s,u) := c(s,u);
f(u,s) :=  c(s,u);

e(u) := c(s,u)
end;

while można zastosować
PUSH lub LIFT do

wybierz PUSH lub LIFT i
wykonaj ;

end;

PREFLOW (G,c,s,t);

{Wyznacza maksymalny przepływ z s do t w sieci (G,c,s,t) }

PUSH (u,v) ;

{ Stosujemy gdy:
e(u) > 0
i c

f

(u,v) > 0

i h(u) = h(v) + 1 }

begin
d

f

(u,v) := min { e(u), c

f

(u,v) };
f(u,v) := f(u,v) + d

f

(u,v);

f(v,u) :=  f(u,v);

e(u) := e(u) - d

f

(u,v);

e(v) := e(v) + d

f

(u,v)

end;

LIFT (u) ;

{ Stosujemy gdy:
e(u) > 0
i



(v



V) jeśli (u,v)



E(G

f

) ,

to h(u) <=
h(v) ) }

begin
h(u) := 1 + min { h(v) : (u,v) 

E(G

f

) }

end;

OPERACJE PUSH I LIFT