Algorytmy i struktury danych
Przeszukiwanie DFS, sortowanie
topologiczne
Mariusz Gł ˛
abowski
Instytut Elektroniki i Telekomunikacji
Politechnika Pozna ´nska
17 pa´zdziernika 2003
dr in˙z. Mariusz Gł ˛
abowski
Algorytmy i struktury danych
Przeszukiwanie DFS, sortowanie
topologiczne
Mariusz Gł ˛
abowski
Instytut Elektroniki i Telekomunikacji
Politechnika Pozna ´nska
17 pa´zdziernika 2003
dr in˙z. Mariusz Gł ˛
abowski
Przeszukiwanie w gł ˛
ab
•
Algorytm przeszukiwania wszerz grafu jest znany tak˙ze jako DFS –
Depth-First Search
•
W czasie przeszukiwania w gł ˛
ab zagł ˛ebiamy si ˛e tak daleko, jak tylko
jest to mo˙zliwe, zanim zajrzymy do innych wierzchołków s ˛
asiednich
•
W algorytmie DFS wierzchołkom przypisuje si ˛e etykiety czasowe
?
d
[
v
]
: numer kroku oblicze ´n, w którym wierzchołek
v
jest odwie-
dzony po raz pierwszy
?
f
[
v
]
: numer kroku w przeszukiwaniu, w którym ko ´nczy si ˛e badanie
listy s ˛
asiedztwa wierzchołka
v
•
DFS tworzy las przeszukiwania w gł ˛
ab zło˙zony z jednego lub wi ˛e-
cej drzew przeszukiwania w gł ˛
ab
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
1
Przeszukiwanie w gł ˛
ab
•
Kolorowanie wierzchołków:
?
biały : wierzchołek nie odwiedzony
?
szary : wierzchołek, który został odwiedzony, ale nie wszystkie
jego kraw ˛edzie zostały zbadane
?
czarny : wierzchołek , który jest przetworzony, tzn. gdy jego lista
s ˛
asiedztwa zostaje całkowicie zbadana
•
Kolorowanie zapewnia, ˙ze ka˙zdy wierzchołek b ˛edzie nale˙zał do do-
kładnie jednego drzewa przeszukiwania w gł ˛
ab
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
2
Przeszukiwanie w gł ˛
ab
•
DFS
(
G
)
1:
for ka˙zdy wierzchołek
u
∈
V
[
G
]
do
2:
color
[
u
] ←
biay
3:
π
[
u
] ←
NIL
4:
end for
5:
time
←
0
6:
for ka˙zdy wierzchołek
u
∈
V
[
G
]
do
7:
if
color
[
u
] =
biay
then
8:
DFS
−
V ISIT
(
u
)
9:
end if
10:
end for
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
3
Przeszukiwanie w gł ˛
ab
•
DFS
−
V ISIT
(
u
)
1:
color
[
u
] ←
szary
2:
/
∗
biały wierzchołek
u
został wła´snie odwiedzony
∗
/
3:
d
[
u
] ←
time
←
time
+
1
4:
for ka˙zdy
v
∈
Adj
[
u
]
do
5:
/
∗
zbadaj kraw ˛ed´z
(
u, v
) ∗
/
6:
if
color
[
v
] =
biay
then
7:
π
[
v
] ←
u
8:
DFS
−
V ISIT
(
v
)
9:
end if
10:
end for
11:
color
[
u
] ←
czarny
/
∗
u
na czarno - został przetworzony
∗
/
12:
f
[
u
] ←
time
←
time
+
1
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
4
Przeszukiwanie DFS - przykład działania
1/
v
u
w
z
y
x
1/
2/
v
u
w
z
y
x
1/
2/
3/
v
u
w
z
y
x
1/
2/
4/
3/
v
u
w
z
y
x
1/
2/
4/
3/
v
u
w
z
y
x
1/
2/
4/5
3/
v
u
w
z
y
x
1/
2/
4/5
3/6
v
u
w
z
y
x
1/
2/7
4/5
3/6
v
u
w
z
y
x
1/
2/7
4/5
3/6
v
u
w
z
y
x
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
5
Przeszukiwanie DFS - przykład działania
1/8
2/7
4/5
3/6
v
u
w
z
y
x
1/8
2/7
4/5
3/6
9/
v
u
w
z
y
x
1/8
2/7
4/5
3/6
9/
v
u
w
z
y
x
1/8
2/7
4/5
3/6
9/
10/
v
u
w
z
y
x
1/8
2/7
4/5
3/6
9/
10/
v
u
w
z
y
x
1/8
2/7
4/5
3/6
9/
10/11
v
u
w
z
y
x
1/8
2/7
4/5
3/6
9/12
10/11
v
u
w
z
y
x
Zło˙zono´s´c czasowa
O
(
V
+
E
)
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
6
Algorytm DFS - klasyfikacja kraw ˛edzi
•
Kraw ˛edzie drzewowe: kraw ˛edzie w lesie przeszukiwania w gł ˛
ab
G
π
; kraw ˛ed´z
(
u, v
)
jest kraw ˛edzi ˛
a drzewow ˛
a, je´sli wierzchołek
v
zo-
stał odwiedzony w wyniku zbadania kraw ˛edziami
(
u, v
)
.
•
Kraw ˛edzie powrotne: kraw ˛edzie
(
u, v
)
, ł ˛
acz ˛
ace wierzchołek
u
z
jego przodkiem
v
w drzewie przeszukiwania w gł ˛
ab. P˛etle s ˛
a trakto-
wane jako kraw ˛edzie powrotne.
•
Kraw ˛edzie w przód: kraw ˛edzie niedrzewowe
(
u, v
)
, które ł ˛
acz ˛
a
wierzchołek
u
z jego potomkiem
v
w drzewie przeszukiwania w gł ˛
ab.
•
Kraw ˛edzie poprzeczne: wszystkie inne kraw ˛edzie. Ł ˛
acz ˛
a one
wierzchołki z tego samego drzewa przeszukiwania w gł ˛
ab, je˙zeli
tylko jeden z wierzchołków nie jest przodkiem drugiego, lub ł ˛
acz ˛
a
wierzchołki z ró˙znych drzew przeszukiwania w gł ˛
ab.
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
7
Własno ´sci algorytmu DFS
3/6
2/9
4/5
7/8
1/10
12/13
z
y
s
v
w
x
11/16
14/15
u
t
T
B
C
F
y
z
x
w
s
v
t
u
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
x
w
y
z
s
t
u
v
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
8
Algorytm DFS - sposób klasyfikacji kraw ˛edzi
•
Ka˙zda kraw ˛ed´z
(
u, v
)
, gdy jest badana po raz pierwszy, mo˙ze zo-
sta´c sklsyfikowana za pomoc ˛
a koloru wierzchołka
v
, do którego pro-
wadzi
(
u, v
)
jest
kraw ˛edzi ˛
a drzewow ˛
a
je˙zeli
v
jest białe
kraw ˛edzi ˛
a powrotn ˛
a
je˙zeli
v
jest szare
kraw ˛edzi ˛
a w przód
je˙zeli
v
jest czarne i
d
[
u
] <
d
[
v
]
kraw ˛edzi ˛
a poprzeczn ˛
a
je˙zeli
v
jest czarne i
d
[
u
] >
d
[
v
]
Twierdzenie 1. W przeszukiwaniu w gł ˛
ab grafu nieskierowanego
G
ka˙zda kraw ˛ed´z jest albo kraw ˛edzi ˛
a drzewow ˛
a, albo kraw ˛edzi ˛
a po-
wrotn ˛
a
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
9
Sortowanie topologiczne
•
Sortowanie topologiczne dagu
G
= (
V, E
)
jest liniowym uporz ˛
ad-
kowaniem wszystkich jego wierzchołków w taki sposób, ˙ze je˙zeli
graf
G
zawiera kraw ˛ed´z
(
u, v
)
, to w tym porz ˛
adku wierzchołek
u
wyst ˛epuje przed wierzchołkiem
v
.
•
Je˙zeli graf nie jest acykliczny, to takie uporz ˛
adkowanie nie jest mo˙z-
liwe.
•
Zastosowania: okre´slenie kolejno´sci wykonywanych czynno´sci.
•
Do sortowania topologiczneg dagów mo˙ze by´c u˙zyte sortowanie w
gł ˛
ab.
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
10
Sortowanie topologiczne
11/16
12/15
6/7
1/8
2/5
3/4
13/14
17/18
9/10
11/16
12/15
6/7
1/8
2/5
3/4
13/14
17/18
9/10
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
11
Algorytm sortowania topologicznego
•
Topological
−
Sort
(
G
)
1. Wykonaj
DFS
(
G
)
w celu obliczenia czasów przetworzenia
f
[
v
]
dla wszystkich wierzchołków
v
2. Wstaw ka˙zdy wierzchołek
v
na pocz ˛
atek listy, kiedy tylko zostanie
przetworzony
3. return lista wierzchołków
•
Analiza czasowa
Θ
(
V
+
E
)
dr in˙z. Mariusz Gł ˛
abowski
Wykład 5 – Przeszukiwanie DFS, sortowanie topologiczne
12