" G = (V, E)
V = {v1, v2, . . . , vn}
E = {e1, e2, . . . , em}
e
(u, v)
"
{u, v}
{u, v} = {v, u} {u, v} {v, u}

(u, v) (v, u)
(u, v) = (v, u)
"
" n
m
Przykłady grafów o rozmiarze n = 6 i m = 8
graf nieskierowany: graf skierowany:
v5
v5
5
v6
v6
v3 v3
8
3
9 9
3
3
v4 v4
8
 8
4
v1
4 v1
4
4
5
5
3
v2
v2
 n � n
i j (i, j)
{i, j}
(i, j)
"
(i, i)
O(n2)
 m � 3
m
O(m)
Przykłady struktur grafowych
[5]
5
[3]
[6]
8
3 9
8
[4]
Lista krawędzi
4
[1]
4
5
[2]
A B W
Macierz wag
(1)
[1] [2] 5
[1] [2] [3] [4] [5] [6]
(2)
[1] [3] 3
[1]
 5 3 4 8 9
(3)
[1] [4] 4
[2]
5  " 4 " 8
(4)
[1] [5] 8
[3]
3 "  " 5 "
(5)
[1] [6] 9
[4]
4 4 "  " " (6)
[2] [4] 4
[5]
(7)
[2] [6] 8
8 " 5 "  "
[6]
(8)
[3] [5] 5
9 8 " " " 
 n
i
i
(i, j)
i j
O(n + m)
 n m
O(n + m)
[5]
[6]
[3]
Przykłady struktur grafowych (c.d.)
3
3
9
[4]
4
[1]
 8
4
5
Pęk wyjściowy
3
[2]
Połączone listy sąsiadów
B W
[2] 5 [3] 3 [4] 4 [6] 9
[1] [1]
1
(1)
[2] 5
[1] 3 [6] -8
[2] [2]
5
(2)
[3] 3
[1] 3
[3] [3]
7
(3)
[4] 4
[4] [2] 4 [4]
8
(4)
[6] 9
[5] [5] -1
[6] [6] -1
(5)
[1] 3
(6)
[6] -8
(7)
[1] 3
(8)
[2] 4
 v1 vk G
{{v1, v2}, {v2, v3}, . . . , {vk-1, vk}}
{v1, v2, . . . , vk-1, vk}
v1 = vk
s t
G = (V , E ) G = (V, E) n d" n m d" m
V ą" V E ą" E G
G
 m = n - 1
T
T = (V , ET )
T
G = (V, E) V = V
nn-2
Przykłady dróg z wierzchołka v5 do v6
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Przykłady dróg z wierzchołka v5 do v6
Droga D1 {v5,v3,v1,v2,v6}
v5
Waga D1: 5+3+5+8 = 21
5
v6
v3
8
6
3
v4
8
v1
4
4
5
v2
Przykłady dróg z wierzchołka v5 do v6
Droga D1 {v5,v3,v1,v2,v6}
v5
Waga D1: 5+3+5+8 = 21
5
v6
v3
8
6
3
Droga D2 {v5,v1,v4,v6}
v4
8
v1
Waga D2: 8+4+6 = 18
4
4
5
v2
Przykłady drzew MST
Drzewo MST1
v5
Waga MST1: 3+8+4+4+6 = 25
5
v6
v3
8
6
3
v4
8
v1
4
4
5
v2
Przykłady drzew MST
Drzewo MST1
v5
Waga MST1: 3+8+4+4+6 = 25
5
v6
v3
8
Drzewo MST2
6
3
Waga MST2: 5+3+5+8+6 = 27
v4
8
v1
4
4
5
v2
 C n
C[i] = i i = 1, 2, . . . , n
 (u, v)
u v
u v
u v C[u] = C[v]
C[v] = C[u]
u v
(u, v)
u v
u C[v] = C[u]
 u v
C[i] = C[v] C[i] == C[u]
(u, v)
C[u] == C[v]
C
 C[u] == C[v] O(1)
n - 2
n/2
O(n)
O(m log m)
 p n - 1
m
O(m log m + pm)
m >> n
O(log m) p
O(p(log m + m)) = O(pm),
n d" p d" m
O(m log m)
Algorytm KRUSKALA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
2. (v2,v4)  4
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
2. (v2,v4)  4
5
v6
v3 3. (v1,v4)  4
8
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
2. (v2,v4)  4
5
v6
v3 3. (v1,v4)  4
8
4. (v1,v2)  cykl
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
2. (v2,v4)  4
5
v6
v3 3. (v1,v4)  4
8
4. (v1,v2)  cykl
9
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
2. (v2,v4)  4
5
v6
v3 3. (v1,v4)  4
8
4. (v1,v2)  cykl
9
5. (v3,v5)  5
3
v4
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
2. (v2,v4)  4
5
v6
v3 3. (v1,v4)  4
8
4. (v1,v2)  cykl
9
5. (v3,v5)  5
3
v4
6. (v2,v6)  8
8
v1
4
4
5
v2
Algorytm KRUSKALA
v5
1. (v1,v3)  3
2. (v2,v4)  4
5
v6
v3 3. (v1,v4)  4
8
4. (v1,v2)  cykl
9
5. (v3,v5)  5
3
v4
6. (v2,v6)  8
8
v1
4
waga MST: 24
4
5
v2
 n - 1
O(m)
O(nm)
 Q
O(m log n)
O(m + n log n)
Algorytm PRIMA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
3. (v1,v4)  4
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
3. (v1,v4)  4
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
3. (v1,v4)  4
4. (v1,v3)  3
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
3. (v1,v4)  4
4. (v1,v3)  3
9
3
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
3. (v1,v4)  4
4. (v1,v3)  3
9
3
5. (v3,v5)  5
v4
8
v1
4
4
5
v2
Algorytm PRIMA
v5
1. (v6,v2)  8
5
2. (v2,v4)  4
v6
v3
8
3. (v1,v4)  4
4. (v1,v3)  3
9
3
5. (v3,v5)  5
v4
8
waga MST: 24
v1
4
4
5
v2
 s
x
dsx
"
dss = 0
 x"
x" dsy y
" " " "
dsx wx y {x", y} dsy = dsx + wx y
Algorytm DIJKSTRY
v5
2
4
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 8 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 12
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v3,v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v3,v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v1,v3,v5,v6}
v2
Algorytm DIJKSTRY
Krok v1 v2 v3 v4 v5 v6
v5
2
4
1 0 5 3 4 8 12
v6
v3
2 0 5 3 4 7 12
8
3 0 5 3 4 7 12
3
12
3
4 0 5 3 4 7 12
5 0 5 3 4 7 9
v4
7
4 6 0 5 3 4 7 9
v1
4
5
3 Najkrótsza droga z v1 do v6:
{ v1,v3,v5,v6}
v2
 n
O(log n)
O(n)
O(n2)
O(m log n)
 n
m
O(nm)
"
"
"
"
Algorytm BELLMANA-FORDA
Q = {v1}
v1 v2 v3 v4 v5 v6
v5
2
4
0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = { }
v1 v2 v3 v4 v5 v6
v5
2
4
0 " " " " "
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v2,v3,v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v3,v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v3,v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 8 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v4,v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v5,v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 12
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = {v6}
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 9
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = { }
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 9
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
Algorytm BELLMANA-FORDA
Q = { }
v1 v2 v3 v4 v5 v6
v5
2
4
0 5 3 4 7 9
v6
v3
8
3
12
3
v4
7
4
v1
4
5
3
v2
 n
n
"
"
 O(nm2)
Algorytm FORDA-FULKERSONA
v5
2
4
v6
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
2
4
v6
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
2
4
v6
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
7
4
v1
4
5
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
0
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
3
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
0
2
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
1
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
4
v1
4
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
0
2
v1
2
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
v1
2
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
v1
2
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
2
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
v4
v1
v2
Algorytm FORDA-FULKERSONA
v5
Przepływy:
2
4
v6 F(v1,v2,v6) = 5
v3
8
F(v1,v3,v5,v6) = 2
F(v1,v4,v2,v6) = 2
3
v4
Maks. przepływ = 9
7
4
v1
4
5
v2